# [472. Concatenated Words](https://leetcode.com/problems/concatenated-words)
[中文文档](/solution/0400-0499/0472.Concatenated%20Words/README.md)
## Description
<p>Given an array of strings <code>words</code> (<strong>without duplicates</strong>), return <em>all the <strong>concatenated words</strong> in the given list of</em> <code>words</code>.</p>
<p>A <strong>concatenated word</strong> is defined as a string that is comprised entirely of at least two shorter words (not necesssarily distinct) in the given array.</p>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
<strong>Output:</strong> ["catsdogcats","dogcatsdog","ratcatdogcat"]
<strong>Explanation:</strong> "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".</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> words = ["cat","dog","catdog"]
<strong>Output:</strong> ["catdog"]
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= words.length <= 10<sup>4</sup></code></li>
<li><code>1 <= words[i].length <= 30</code></li>
<li><code>words[i]</code> consists of only lowercase English letters.</li>
<li>All the strings of <code>words</code> are <strong>unique</strong>.</li>
<li><code>1 <= sum(words[i].length) <= 10<sup>5</sup></code></li>
</ul>
## Solutions
<!-- tabs:start -->
### **Python3**
```python
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
```
### **Java**
```java
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;
}
}
```
### **C++**
```cpp
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;
}
};
```
### **Go**
```go
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
}
```
### **...**
```
```
<!-- tabs:end -->