472. Concatenated Words
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 in the given array.
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
| struct Trie{
Trie* next[26];
bool eof;
Trie(): eof(false) {
memset(next,0,sizeof(next));
}
};
class Solution {
Trie* root;
void insert(string& word) {
Trie* trie = root;
for(auto ch : word) {
if(!trie->next[ch-'a'])
trie->next[ch-'a'] = new Trie();
trie = trie->next[ch-'a'];
}
trie->eof = true;
}
bool find(string& word, int i, bool concated = false) {
Trie* trie = root;
while(i < word.length()) {
if(!trie->next[word[i]-'a']) return false;
trie = trie->next[word[i++]-'a'];
if(trie->eof) {
if(i == word.length()) return concated;
else if(find(word, i, true))
return true;
}
}
return false;
}
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
root = new Trie();
vector<string> res;
for(auto& word : words)
insert(word);
for(auto& word : words)
if(find(word, 0))
res.push_back(word);
return res;
}
};
|
