-
Notifications
You must be signed in to change notification settings - Fork 28
/
Concatenated_Words.cpp
28 lines (27 loc) · 926 Bytes
/
Concatenated_Words.cpp
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
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> wordSet(words.begin(), words.end());
vector<string> result;
int n = (int)words.size();
for(int i = 0; i < n; i++) {
int m = (int)words[i].length();
vector<bool> dp(m + 1, false);
dp[0] = true;
for(int j = 0; j < m; j++) {
if(dp[j]) {
for(int len = 1; len <= min(m - j, m - 1); len++) {
if(wordSet.count(words[i].substr(j, len))) {
dp[j + len] = true;
}
}
if(dp[m]) {
result.push_back(words[i]);
break;
}
}
}
}
return result;
}
};