Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/472.html
472. Concatenated Words (Hard)
Given a list of words (without duplicates), please write a program that returns all 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.
Example:
Input: ["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".
Note:
- The number of elements of the given array will not exceed
10,000 - The length sum of elements in the given array will not exceed
600,000. - All the input string will only include lower case letters.
- The returned elements order does not matter.
Related Topics:
Dynamic Programming, Depth-first Search, Trie
Similar Questions:
Solution 1. Trie + C++ Static Pool
Use Trie to store the words.
Use DFS to check whether a word is a concatenated word: traverse from the first letter in word, whenever we meet an word ending, start a new DFS call and re-search from the trie root. If the word is exhausted by matching at least two words, return true; otherwise return false.
// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*2^W) where N is length of words array, W is max word length.
// 2^W is because for each letter we may start or not start a new check there.
// Space: O(C) where C is the length sum of words.
// Ref: https://discuss.leetcode.com/topic/72754/trie-dfs-method-using-static-trie-node-to-avoid-getting-mle-runtime-about-300ms
// NOTE: Use statically allocated memory to avoid MLE in C++.
class TrieNode {
public:
bool end = false;
TrieNode *next[26];
};
TrieNode pool[60000];
class Solution {
private:
TrieNode *root = pool;
int cnt = 1;
void insert(string &word) {
TrieNode *node = root;
for (char c : word) {
if (!node->next[c - 'a']) node->next[c - 'a'] = &pool[cnt++];
node = node->next[c - 'a'];
}
node->end = true;
}
bool check(string &word, int start) {
if (start == word.size()) return true;
TrieNode *node = root;
for (int i = start; i < word.size(); ++i) {
node = node->next[word[i] - 'a'];
if (!node) return false;
if (i != word.size() - 1 && node->end && check(word, i + 1)) return true;
}
return node->end && start;
}
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
memset(pool, 0, sizeof(pool)); // reset pool.
for (string s : words) insert(s);
vector<string> ans;
for (string s : words) {
if (s.empty()) continue;
if (check(s, 0)) ans.push_back(s);
}
return ans;
}
};
Solution 2: Trie + unordered_map
Same idea as Solution 1, instead of using statically allocated pool, use unordered_map to store children mapping in TrieNode.
// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*2^W) where N is length of words array, W is max word length.
// 2^W is because for each letter we may start or not start a new check there.
// Space: O(C) where C is the length sum of words.
// NOTE: use `unordered_map` instead of `TrieNode*[26]` to save space.
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isWord = false;
};
class Trie {
private:
TrieNode root;
bool dfs(string &word, int start, int cnt) {
if (start == word.size()) return cnt > 1;
TrieNode *node = &root;
for (int i = start; i < word.size(); ++i) {
if (node->children.find(word[i]) == node->children.end()) return false;
TrieNode *next = node->children[word[i]];
if (next->isWord && dfs(word, i + 1, cnt + 1)) return true;
node = next;
}
return false;
}
public:
void insert(string &word) {
TrieNode *node = &root;
for (char c : word) {
if (!node->children[c]) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isWord = true;
}
bool isConcatednatedWord(string &word) {
return dfs(word, 0, 0);
}
};
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
Trie trie;
for (auto word : words) trie.insert(word);
vector<string> ans;
for (auto word : words) {
if (trie.isConcatednatedWord(word)) ans.push_back(word);
}
return ans;
}
};
Solution 3. DP
Use dp[i] to denote whether word[0..i] is a concatenated word.
dp[i] = true, if there is a j ∈ [0,i] such that word[0..j] and word[j..i] are all words in words array.
In my opinion, this is just doing DFS in another way.
// OJ: https://leetcode.com/problems/concatenated-words/
// Time: O(N*W^3)
// Space: O(C) where C is the length sum of words.
// Ref: https://discuss.leetcode.com/topic/72393/c-772-ms-dp-solution
class Solution {
private:
unordered_set<string> s;
bool isConcatenatedWord(string &word) {
int W = word.size();
vector<bool> dp(W, false);
for (int i = 0; i < W - 1; ++i) {
if (s.count(word.substr(0, i + 1))) dp[i] = true;
if (!dp[i]) continue;
for (int j = i + 1; j < W; ++j) {
if (s.count(word.substr(i + 1, j - i))) dp[j] = true;
}
if (dp[W - 1]) return true;
}
return false;
}
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
s = unordered_set<string>(words.begin(), words.end());
vector<string> ans;
for (string &word : words) {
if (isConcatenatedWord(word)) ans.push_back(word);
}
return ans;
}
};
-
class Solution { TrieNode root = new TrieNode(); public List<String> findAllConcatenatedWordsInADict(String[] words) { List<String> concatenateWords = new ArrayList<String>(); if (words == null || words.length == 0) return concatenateWords; for (String word : words) { if (word.length() > 0) insert(word); } for (String word: words) { if (depthFirstSearch(word, root, 0, 0)) concatenateWords.add(word); } return concatenateWords; } public void insert(String word) { TrieNode node = root; int length = word.length(); for (int i = 0; i < length; i++) { int index = word.charAt(i) - 'a'; if (node.next[index] == null) node.next[index] = new TrieNode(); node = node.next[index]; } node.wordEnd = true; } public boolean depthFirstSearch(String word, TrieNode node, int count, int start) { int length = word.length(); for (int i = start; i < length; i++) { int index = word.charAt(i) - 'a'; if (node.next[index] == null) return false; node = node.next[index]; if (node.wordEnd && depthFirstSearch(word, root, count + 1, i + 1)) return true; } return count > 0 && node.wordEnd; } } class TrieNode { boolean wordEnd; TrieNode[] next; public TrieNode() { wordEnd = false; next = new TrieNode[26]; } } -
// OJ: https://leetcode.com/problems/concatenated-words/ // Time: O(N * W^2) // Space: O(NW) struct TrieNode { TrieNode *next[26] = {}; bool end = false; }; class Solution { TrieNode root; void addWord(TrieNode *node, string &s) { for (char c : s) { if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode(); node = node->next[c - 'a']; } node->end = true; } bool valid(string &s) { int N = s.size(); vector<bool> dp(N + 1); dp[0] = true; for (int i = 0; i < N && !dp[N]; ++i) { if (!dp[i]) continue; auto node = &root; for (int j = i; j < N - (i == 0); ++j) { node = node->next[s[j] - 'a']; if (!node) break; if (node->end) dp[j + 1] = true; } } return dp[N]; } public: vector<string> findAllConcatenatedWordsInADict(vector<string>& A) { for (auto &s : A) { if (s.empty()) continue; addWord(&root, s); } vector<string> ans; for (auto &s : A) { if (s.size() && valid(s)) ans.push_back(s); } return ans; } }; -
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 ############ class Solution(object): def findAllConcatenatedWordsInADict(self, words): """ :type words: List[str] :rtype: List[str] """ def wordBreak(word, cands): if not cands: return False dp = [False] * (len(word) + 1) dp[0] = True for i in range(1, len(word) + 1): for j in reversed(range(0, i)): if not dp[j]: continue if word[j:i] in cands: dp[i] = True break return dp[-1] words.sort(key=lambda x: -len(x)) cands = set(words) ans = [] for i in range(0, len(words)): cands -= {words[i]} if wordBreak(words[i], cands): ans += words[i], return ans