Trie
Array
Hash Table
String
Description
In English, we have a concept called root , which can be followed by some other word to form another longer word - let's call this word derivative . For example, when the root "help"
is followed by the word "ful"
, we can form a derivative "helpful"
.
Given a dictionary
consisting of many roots and a sentence
consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root , replace it with the root that has the shortest length .
Return the sentence
after the replacement.
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Example 2:
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
Constraints:
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i]
consists of only lower-case letters.
1 <= sentence.length <= 106
sentence
consists of only lower-case letters and spaces.
The number of words in sentence
is in the range [1, 1000]
The length of each word in sentence
is in the range [1, 1000]
Every two consecutive words in sentence
will be separated by exactly one space.
sentence
does not have leading or trailing spaces.
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 class Trie :
def __init__ ( self ):
self . children : List [ Trie | None ] = [ None ] * 26
self . ref : int = - 1
def insert ( self , w : str , i : int ):
node = self
for c in w :
idx = ord ( c ) - ord ( "a" )
if node . children [ idx ] is None :
node . children [ idx ] = Trie ()
node = node . children [ idx ]
node . ref = i
def search ( self , w : str ) -> int :
node = self
for c in w :
idx = ord ( c ) - ord ( "a" )
if node . children [ idx ] is None :
return - 1
node = node . children [ idx ]
if node . ref != - 1 :
return node . ref
return - 1
class Solution :
def replaceWords ( self , dictionary : List [ str ], sentence : str ) -> str :
trie = Trie ()
for i , w in enumerate ( dictionary ):
trie . insert ( w , i )
ans = []
for w in sentence . split ():
idx = trie . search ( w )
ans . append ( dictionary [ idx ] if idx != - 1 else w )
return " " . join ( ans )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public String replaceWords ( List < String > dictionary , String sentence ) {
Set < String > s = new HashSet <> ( dictionary );
String [] words = sentence . split ( " " );
for ( int i = 0 ; i < words . length ; ++ i ) {
String word = words [ i ] ;
for ( int j = 1 ; j <= word . length (); ++ j ) {
String t = word . substring ( 0 , j );
if ( s . contains ( t )) {
words [ i ] = t ;
break ;
}
}
}
return String . join ( " " , words );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 class Trie {
private :
Trie * children [ 26 ];
int ref ;
public :
Trie ()
: ref ( -1 ) {
memset ( children , 0 , sizeof ( children ));
}
void insert ( const string & w , int i ) {
Trie * node = this ;
for ( auto & c : w ) {
int idx = c - 'a' ;
if ( ! node -> children [ idx ]) {
node -> children [ idx ] = new Trie ();
}
node = node -> children [ idx ];
}
node -> ref = i ;
}
int search ( const string & w ) {
Trie * node = this ;
for ( auto & c : w ) {
int idx = c - 'a' ;
if ( ! node -> children [ idx ]) {
return -1 ;
}
node = node -> children [ idx ];
if ( node -> ref != -1 ) {
return node -> ref ;
}
}
return -1 ;
}
};
class Solution {
public :
string replaceWords ( vector < string >& dictionary , string sentence ) {
Trie * trie = new Trie ();
for ( int i = 0 ; i < dictionary . size (); ++ i ) {
trie -> insert ( dictionary [ i ], i );
}
stringstream ss ( sentence );
string w ;
string ans ;
while ( ss >> w ) {
int idx = trie -> search ( w );
ans += ( idx == -1 ? w : dictionary [ idx ]) + " " ;
}
ans . pop_back ();
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 type Trie struct {
children [ 26 ] * Trie
ref int
}
func newTrie () * Trie {
return & Trie { ref : - 1 }
}
func ( this * Trie ) insert ( w string , i int ) {
node := this
for _ , c := range w {
idx := c - 'a'
if node . children [ idx ] == nil {
node . children [ idx ] = newTrie ()
}
node = node . children [ idx ]
}
node . ref = i
}
func ( this * Trie ) search ( w string ) int {
node := this
for _ , c := range w {
idx := c - 'a'
if node . children [ idx ] == nil {
return - 1
}
node = node . children [ idx ]
if node . ref != - 1 {
return node . ref
}
}
return - 1
}
func replaceWords ( dictionary [] string , sentence string ) string {
trie := newTrie ()
for i , w := range dictionary {
trie . insert ( w , i )
}
ans := strings . Builder {}
for _ , w := range strings . Split ( sentence , " " ) {
if idx := trie . search ( w ); idx != - 1 {
ans . WriteString ( dictionary [ idx ])
} else {
ans . WriteString ( w )
}
ans . WriteByte ( ' ' )
}
return ans . String ()[: ans . Len () - 1 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 class Trie {
# children : Record < string , Trie > = {};
# ref = - 1 ;
insert ( w : string , i : number ) {
let node : Trie = this ;
for ( const c of w ) {
node . # children [ c ] ??= new Trie ();
node = node . # children [ c ];
}
node . # ref = i ;
}
search ( w : string ) : number {
let node : Trie = this ;
for ( const c of w ) {
if ( ! node . # children [ c ]) {
return - 1 ;
}
node = node . # children [ c ];
if ( node . # ref !== - 1 ) {
return node . # ref ;
}
}
return - 1 ;
}
}
function replaceWords ( dictionary : string [], sentence : string ) : string {
const trie = new Trie ();
for ( let i = 0 ; i < dictionary . length ; i ++ ) {
trie . insert ( dictionary [ i ], i );
}
return sentence
. split ( ' ' )
. map ( w => {
const idx = trie . search ( w );
return idx !== - 1 ? dictionary [ idx ] : w ;
})
. join ( ' ' );
}
Solution 2
GitHub