472. Concatenated Words
1. Description
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.
2. Example
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”]
3. Constraints
- 1 <= words.length <= $10^4$
- 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) <= $10^5$
4. Solutions
Trie & Depth-First Search
n = words.size(), $l_i$ is the length of a word
Time complexity: O(nlogn + $\sum_{0<=i<=n}l_i$)
Space complexity: O($\sum_{0<=i<=n}l_i$)
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
sort(words.begin(), words.end(), [&](const string &a, const string &b) {
// the compare function doesn't allow =
return a.size() < b.size();
});
vector<string> result;
for (auto word : words) {
if (word.size() > 0) {
find_word_(word, 0) ? result.push_back(move(word)) : insert_word_(word);
}
}
return result;
}
private:
struct Trie {
bool is_end;
array<Trie *, 26> children;
Trie() {
is_end = false;
children.fill(nullptr);
}
};
Trie *trie_ = new Trie();
int get_index_(char letter) {
return letter - 'a';
}
bool find_word_(const string &word, int index) {
if (index == word.size()) {
return true;
}
Trie *trie = trie_;
for (int i = index; i < word.size(); ++i) {
trie = trie->children[get_index_(word[i])];
if (trie == nullptr) {
return false;
}
if (trie->is_end) {
if (find_word_(word, i + 1)) {
return true;
}
}
}
return false;
}
void insert_word_(const string &word) {
Trie *trie = trie_;
for (char letter : word) {
if (trie->children[get_index_(letter)] == nullptr) {
trie->children[get_index_(letter)] = new Trie();
}
trie = trie->children[get_index_(letter)];
}
trie->is_end = true;
}
};