Depth-First Search
Trie
Array
String
Dynamic Programming
Description
Given an array of strings words
(without duplicates ), return all the concatenated words in the given list of words
.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Example 2:
Input: words = ["cat","dog","catdog"]
Output: ["catdog"]
Constraints:
1 <= words.length <= 104
1 <= words[i].length <= 30
words[i]
consists of only lowercase English letters.
All the strings of words
are unique .
1 <= sum(words[i].length) <= 105
Solutions
Solution 1
Python3 Java C++ Go
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 class Trie :
def __init__ ( self ):
self . children = [ None ] * 26
self . is_end = False
def insert ( self , w ):
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 . is_end = True
class Solution :
def findAllConcatenatedWordsInADict ( self , words : List [ str ]) -> List [ str ]:
def dfs ( w ):
if not w :
return True
node = trie
for i , c in enumerate ( w ):
idx = ord ( c ) - ord ( 'a' )
if node . children [ idx ] is None :
return False
node = node . children [ idx ]
if node . is_end and dfs ( w [ i + 1 :]):
return True
return False
trie = Trie ()
ans = []
words . sort ( key = lambda x : len ( x ))
for w in words :
if dfs ( w ):
ans . append ( w )
else :
trie . insert ( w )
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 class Trie {
Trie [] children = new Trie [ 26 ] ;
boolean isEnd ;
void insert ( String w ) {
Trie node = this ;
for ( char c : w . toCharArray ()) {
c -= 'a' ;
if ( node . children [ c ] == null ) {
node . children [ c ] = new Trie ();
}
node = node . children [ c ] ;
}
node . isEnd = true ;
}
}
class Solution {
private Trie trie = new Trie ();
public List < String > findAllConcatenatedWordsInADict ( String [] words ) {
Arrays . sort ( words , ( a , b ) -> a . length () - b . length ());
List < String > ans = new ArrayList <> ();
for ( String w : words ) {
if ( dfs ( w )) {
ans . add ( w );
} else {
trie . insert ( w );
}
}
return ans ;
}
private boolean dfs ( String w ) {
if ( "" . equals ( w )) {
return true ;
}
Trie node = trie ;
for ( int i = 0 ; i < w . length (); ++ i ) {
int idx = w . charAt ( i ) - 'a' ;
if ( node . children [ idx ] == null ) {
return false ;
}
node = node . children [ idx ] ;
if ( node . isEnd && dfs ( w . substring ( i + 1 ))) {
return true ;
}
}
return false ;
}
}
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 class Trie {
public :
vector < Trie *> children ;
bool isEnd ;
Trie ()
: children ( 26 )
, isEnd ( false ) {}
void insert ( string w ) {
Trie * node = this ;
for ( char c : w ) {
c -= 'a' ;
if ( ! node -> children [ c ]) node -> children [ c ] = new Trie ();
node = node -> children [ c ];
}
node -> isEnd = true ;
}
};
class Solution {
public :
Trie * trie = new Trie ();
vector < string > findAllConcatenatedWordsInADict ( vector < string >& words ) {
sort ( words . begin (), words . end (), [ & ]( const string & a , const string & b ) {
return a . size () < b . size ();
});
vector < string > ans ;
for ( auto & w : words ) {
if ( dfs ( w ))
ans . push_back ( w );
else
trie -> insert ( w );
}
return ans ;
}
bool dfs ( string w ) {
if ( w == "" ) return true ;
Trie * node = trie ;
for ( int i = 0 ; i < w . size (); ++ i ) {
int idx = w [ i ] - 'a' ;
if ( ! node -> children [ idx ]) return false ;
node = node -> children [ idx ];
if ( node -> isEnd && dfs ( w . substr ( i + 1 ))) return true ;
}
return false ;
}
};
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 type Trie struct {
children [ 26 ] * Trie
isEnd bool
}
func newTrie () * Trie {
return & Trie {}
}
func ( this * Trie ) insert ( word string ) {
node := this
for _ , c := range word {
c -= 'a'
if node . children [ c ] == nil {
node . children [ c ] = newTrie ()
}
node = node . children [ c ]
}
node . isEnd = true
}
func findAllConcatenatedWordsInADict ( words [] string ) ( ans [] string ) {
sort . Slice ( words , func ( i , j int ) bool { return len ( words [ i ]) < len ( words [ j ]) })
trie := newTrie ()
var dfs func ( string ) bool
dfs = func ( w string ) bool {
if w == "" {
return true
}
node := trie
for i , c := range w {
c -= 'a'
if node . children [ c ] == nil {
return false
}
node = node . children [ c ]
if node . isEnd && dfs ( w [ i + 1 :]) {
return true
}
}
return false
}
for _ , w := range words {
if dfs ( w ) {
ans = append ( ans , w )
} else {
trie . insert ( w )
}
}
return
}
GitHub