I like to read this solution as a small machine: keep the useful information, throw away the noise. For 472. Concatenated Words, the solution in this repository is mainly a trie solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: trie, DFS + memoization, dynamic programming, stack.
The notes already sitting in the source point us in the right direction:
- Trie + BFS
- TLE
- 43 / 44 test cases passed.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are add, findPrefixes, findAllConcatenatedWordsInADict, test, wordBreak.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Trie + BFS
02//TLE
03//43 / 44 test cases passed.
04class TrieNode{
05public:
06 vector<TrieNode*> children;
07 string word;
08
09 TrieNode(){
10 children = vector<TrieNode*>(26, nullptr);
11 }
12};
13
14class Trie{
15public:
16 TrieNode* root;
17
18 Trie(){
19 root = new TrieNode();
20 }
21
22 void add(string& word){
23 TrieNode* cur = root;
24
25 for(char& c : word){
26 if(cur->children[c-'a'] == nullptr){
27 cur->children[c-'a'] = new TrieNode();
28 }
29
30 cur = cur->children[c-'a'];
31 }
32
33 cur->word = word;
34 }
35
36 /*
37 find all prefixes of "word",
38 note that the word itself is also considered as a prefix
39 */
40 void findPrefixes(string& word, queue<pair<string, int>>& prefixes){
41 TrieNode* cur = root;
42
43 for(char& c : word){
44 cur = cur->children[c-'a'];
45
46 if(cur == nullptr){
47 break;
48 }
49
50 if(!cur->word.empty()){ //a.k.a isEnd
51 prefixes.push({cur->word, word.size() - cur->word.size()});
52 }
53 }
54 }
55};
56
57class Solution {
58public:
59 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
60 Trie* trie = new Trie();
61
62 for(int i = 0; i < words.size(); ++i){
63 trie->add(words[i]);
64 }
65
66 vector<string> ans;
67
68 for(string& word : words){
69 // cout << "word: " << word << endl;
70 //(word, remain)
71 queue<pair<string, int>> prefixes;
72
73 //fill prefixes
74 trie->findPrefixes(word, prefixes);
75
76 while(!prefixes.empty()){
77 pair<string, int> p = prefixes.front(); prefixes.pop();
78 // cout << p.first << ", " << p.second << endl;
79 if(p.second == 0 && p.first != word){
80 //p.second == 0: the remaining unmatched substring's size
81 //p.first != word: avoid the case that we find the string itself
82 ans.push_back(word);
83 break;
84 }else{
85 //"remain"'s size is p.second
86 string remain = word.substr(word.size()-p.second);
87 trie->findPrefixes(remain, prefixes);
88 }
89 }
90 }
91
92 return ans;
93 }
94};
95
96//Trie + DFS
97//Runtime: 1412 ms, faster than 10.95% of C++ online submissions for Concatenated Words.
98//Memory Usage: 654.2 MB, less than 5.39% of C++ online submissions for Concatenated Words.
99class TrieNode{
100public:
101 vector<TrieNode*> children;
102 string word;
103
104 TrieNode(){
105 children = vector<TrieNode*>(26, nullptr);
106 }
107};
108
109class Trie{
110public:
111 TrieNode* root;
112
113 Trie(){
114 root = new TrieNode();
115 }
116
117 void add(string& word){
118 TrieNode* cur = root;
119
120 for(char& c : word){
121 if(cur->children[c-'a'] == nullptr){
122 cur->children[c-'a'] = new TrieNode();
123 }
124
125 cur = cur->children[c-'a'];
126 }
127
128 cur->word = word;
129 }
130
131 /*
132 find all prefixes of "word",
133 note that the word itself is also considered as a prefix
134 */
135 void findPrefixes(string& word, stack<pair<string, int>>& prefixes){
136 TrieNode* cur = root;
137
138 for(char& c : word){
139 cur = cur->children[c-'a'];
140
141 if(cur == nullptr){
142 break;
143 }
144
145 if(!cur->word.empty()){ //a.k.a isEnd
146 prefixes.push({cur->word, word.size() - cur->word.size()});
147 }
148 }
149 }
150};
151
152class Solution {
153public:
154 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
155 Trie* trie = new Trie();
156
157 for(int i = 0; i < words.size(); ++i){
158 trie->add(words[i]);
159 }
160
161 vector<string> ans;
162
163 for(string& word : words){
164 // cout << "word: " << word << endl;
165 //(word, remain)
166 stack<pair<string, int>> prefixes;
167
168 //fill prefixes
169 trie->findPrefixes(word, prefixes);
170
171 while(!prefixes.empty()){
172 pair<string, int> p = prefixes.top(); prefixes.pop();
173 // cout << p.first << ", " << p.second << endl;
174 if(p.second == 0 && p.first != word){
175 //p.second == 0: the remaining unmatched substring's size
176 //p.first != word: avoid the case that we find the string itself
177 ans.push_back(word);
178 break;
179 }else{
180 //"remain"'s size is p.second
181 string remain = word.substr(word.size()-p.second);
182 trie->findPrefixes(remain, prefixes);
183 }
184 }
185 }
186
187 return ans;
188 }
189};
190
191//Trie + DFS, optimized
192//https://leetcode.com/problems/concatenated-words/discuss/95644/102ms-java-Trie-%2B-DFS-solution.-With-explanation-easy-to-understand.
193//Runtime: 488 ms, faster than 78.18% of C++ online submissions for Concatenated Words.
194//Memory Usage: 290.5 MB, less than 36.74% of C++ online submissions for Concatenated Words.
195class TrieNode{
196public:
197 vector<TrieNode*> children;
198 string word;
199
200 TrieNode(){
201 children = vector<TrieNode*>(26, nullptr);
202 }
203};
204
205class Trie{
206public:
207 TrieNode* root;
208
209 Trie(){
210 root = new TrieNode();
211 }
212
213 void add(string& word){
214 TrieNode* cur = root;
215
216 for(char& c : word){
217 if(cur->children[c-'a'] == nullptr){
218 cur->children[c-'a'] = new TrieNode();
219 }
220
221 cur = cur->children[c-'a'];
222 }
223
224 cur->word = word;
225 }
226
227 /*
228 find all prefixes of "word",
229 note that the word itself is also considered as a prefix
230 */
231 bool test(string& word, int start, int& count){
232 TrieNode* cur = root;
233
234 for(int i = start; i < word.size(); ++i){
235 char c = word[i];
236 cur = cur->children[c-'a'];
237
238 if(cur == nullptr){
239 break;
240 }
241
242 if(!cur->word.empty()){ //a.k.a isEnd
243 ++count;
244 if(i == word.size()-1){
245 //constructed by more than 1 words
246 return count > 1;
247 }
248 if(test(word, i+1, count)){
249 return true;
250 }
251 --count;
252 }
253 }
254
255 return false;
256 }
257};
258
259class Solution {
260public:
261 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
262 Trie* trie = new Trie();
263
264 for(int i = 0; i < words.size(); ++i){
265 trie->add(words[i]);
266 }
267
268 vector<string> ans;
269
270 for(string& word : words){
271 // cout << "word: " << word << endl;
272 if(word.empty()) continue;
273 int count = 0;
274 if(trie->test(word, 0, count)){
275 ans.push_back(word);
276 }
277 }
278
279 return ans;
280 }
281};
282
283//DP, Word Break I
284//https://leetcode.com/problems/concatenated-words/discuss/95652/Java-DP-Solution
285//TLE
286//6 / 44 test cases passed.
287class Solution {
288public:
289 bool wordBreak(string s, unordered_set<string>& wordDict) {
290 if(wordDict.empty())
291 return false;
292
293 int n = s.size();
294
295 //key: end index, 1-based
296 vector<bool> dp(n+1, false);
297 //empty string
298 dp[0] = true;
299
300 for(int end = 1; end <= n; ++end){
301 for(int start = 0; start < end; ++start){
302 //dp[start]: s[0...start-1]
303 if(dp[start] && find(wordDict.begin(), wordDict.end(), s.substr(start, end-start)) != wordDict.end()){
304 //s[0...end-1] can be split into s[0...start-1] and s[start...end-1]
305 dp[end] = true;
306 break;
307 }
308 }
309 }
310
311 return dp[n];
312 }
313
314 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
315 int n = words.size();
316
317 vector<string> ans;
318
319 sort(words.begin(), words.end(), [](const string& w1, const string& w2){
320 return w1.size() < w2.size();
321 });
322
323 unordered_set<string> preWords;
324 for(string& word : words){
325 if(wordBreak(word, preWords)){
326 ans.push_back(word);
327 }
328 preWords.insert(word);
329 }
330
331 return ans;
332 }
333};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.