Given an array of string 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.
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
To solve this problem, you can use a combination of a Trie data structure and dynamic programming.
- First, create a Trie data structure with all the words in the input array.
- Next, for each word in the array, perform a depth-first search on the Trie to check if it can be formed by concatenating other words in the Trie.
- Use dynamic programming to store the results of the search for each word, to avoid recalculating the same sub-problems multiple times.
- Finally, return the list of words that can be formed by concatenating other words in the Trie.
The time complexity of this approach is O(n*L^2) where n is the number of words in the array and L is the maximum length of a word. The space complexity is O(nL) for storing the Trie and the dynamic programming array.
class Solution {
public:
struct TrieNode {
bool isEnd;
unordered_map<char, TrieNode*> children;
TrieNode() : isEnd(false) {}
};
TrieNode* root;
vector<string> ans;
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
root = new TrieNode();
for (string& word : words) {
TrieNode* curr = root;
for (char c : word) {
if (!curr->children[c]) curr->children[c] = new TrieNode();
curr = curr->children[c];
}
curr->isEnd = true;
}
unordered_map<string, bool> dp;
for (string& word : words) {
if (word.empty()) continue;
dp.clear();
dp[word] = true;
if (search(root, dp, word)) ans.push_back(word);
}
return ans;
}
bool search(TrieNode* curr, unordered_map<string, bool>& dp, string& word) {
for (int i = 0; i < word.size(); i++) {
string suffix = word.substr(i);
if (!curr->children[suffix[0]]) return false;
curr = curr->children[suffix[0]];
if (curr->isEnd && dp.count(suffix) == 0 && search(root, dp, suffix)) {
dp[suffix] = true;
return true;
}
}
return false;
}
};