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 (not necessarily distinct) 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 <= 1041 <= words[i].length <= 30words[i] consists of only lowercase English letters.- All the strings of
words are unique.
1 <= sum(words[i].length) <= 105
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
class Trie {
Trie[] children = new Trie[26];
boolean isEnd;
void insert(String w) {
Trie node = this;
for (char c : w.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
}
node.isEnd = true;
}
}
class Solution {
private Trie trie = new Trie();
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
List<String> ans = new ArrayList<>();
for (String w : words) {
if (dfs(w)) {
ans.add(w);
} else {
trie.insert(w);
}
}
return ans;
}
private boolean dfs(String w) {
if ("".equals(w)) {
return true;
}
Trie node = trie;
for (int i = 0; i < w.length(); ++i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
return false;
}
node = node.children[idx];
if (node.isEnd && dfs(w.substring(i + 1))) {
return true;
}
}
return false;
}
}(code-box)
class Trie {
public:
vector<Trie*> children;
bool isEnd;
Trie()
: children(26)
, isEnd(false) {}
void insert(string w) {
Trie* node = this;
for (char c : w) {
c -= 'a';
if (!node->children[c]) node->children[c] = new Trie();
node = node->children[c];
}
node->isEnd = true;
}
};
class Solution {
public:
Trie* trie = new Trie();
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
sort(words.begin(), words.end(), [&](const string& a, const string& b) {
return a.size() < b.size();
});
vector<string> ans;
for (auto& w : words) {
if (dfs(w))
ans.push_back(w);
else
trie->insert(w);
}
return ans;
}
bool dfs(string w) {
if (w == "") return true;
Trie* node = trie;
for (int i = 0; i < w.size(); ++i) {
int idx = w[i] - 'a';
if (!node->children[idx]) return false;
node = node->children[idx];
if (node->isEnd && dfs(w.substr(i + 1))) return true;
}
return false;
}
};(code-box)
type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func findAllConcatenatedWordsInADict(words []string) (ans []string) {
sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
trie := newTrie()
var dfs func(string) bool
dfs = func(w string) bool {
if w == "" {
return true
}
node := trie
for i, c := range w {
c -= 'a'
if node.children[c] == nil {
return false
}
node = node.children[c]
if node.isEnd && dfs(w[i+1:]) {
return true
}
}
return false
}
for _, w := range words {
if dfs(w) {
ans = append(ans, w)
} else {
trie.insert(w)
}
}
return
}(code-box)
