# 0472. 连接词
### 题目地址（472. 连接词）
### 题目描述
```
给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。
连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
示例:
输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]
解释: "catsdogcats"由"cats", "dog" 和 "cats"组成;
"dogcatsdog"由"dog", "cats"和"dog"组成;
"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
说明:
给定数组的元素总数不超过 10000。
给定数组中元素的长度总和不超过 600000。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。
```
### 前置知识
* [前缀树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/trie)
### 公司
* 阿里
* 字节
### 思路
本题我的思路是直接使用前缀树来解决。**标准的前缀树模板**我在之前的题解中提到了，感兴趣的可以到下方的相关题目中查看。
这道题这里我们不需要 search，我们的做法是：
* 先进行一次遍历，将 words 全部插入（insert）到前缀树中。
* 然后再进行一次遍历，查找每一个单词有几个单词表中的单词组成
* 如果大于 2，则将其加入到 res 中
* 最后返回 res 即可
我们构造的前缀树大概是这样的：
问题的关键在于第二步中的**查找每一个单词有几个单词表中的单词组成**。 其实如果你了解前缀树的话应该不难写出来。 比如查找 catsdogcats：
* 我们先从 c 到 a 到 t，发现 t 是单词结尾，我们数量 + 1
* 然后将剩下的部分“sdogcats”重新执行上述过程。
* s 发现找不到，我们返回 0
* 因此最终结果是 1
很明显这个逻辑是错误的，正确的划分应该是：
* 我们先从 c 到 a 到 t，再到 s，此时数量 + 1
* 然后将剩下的“dogcats”重复上述过程
* dog 找到了，数量 + 1
* 最后将 cats 加入。也找到了，数量再加 1
由于我们并不知道 cat 这里断开，结果更大？还是 cats 这里断开结果更大？因此我们的做法是将其全部递归求出，然后取出最大值即可。如果我们直接这样递归的话，可能会超时，卡在最后一个测试用例上。一个简单的方式是记忆化递归，从而避免重复计算，经测试这种方法能够通过。
2021-12-28 updated: 由于力扣增加了测试用例，导致了上面的仅仅依靠记忆化也是无法 AC 的。需要进一步优化。
我们可以将 words 排序，这样就可以剪枝了。如何剪枝呢？直接用代码比较直观：
```py
for word in words:
if trie.cntWords(word) >= 2:
res.append(word)
else:
trie.insert(word)
```
如果如果 word 是合成词，那么没有必要将其加到 trie 中，因为这不影响答案，最多就是 cntWords 算出来的数字不对了。不过这道题对具体的数字不感兴趣，我们只关心是否大于 2。
需要注意的是， 一定要排序。 否则如果合成词在前就没有优化效果了，达不到剪枝的目的。
### 关键点分析
* 前缀树
* 记忆化搜索
* 排序后 word **选择性**插入到 trie 中
### 代码
代码支持：Python3
Python3 Code:
```python
class Trie:
def __init__(self):
self.Trie = {}
self.visited = {}
def insert(self, word):
curr = self.Trie
for w in word:
if w not in curr:
curr[w] = {}
curr = curr[w]
curr['#'] = 1
def cntWords(self, word):
if not word:
return 0
if word in self.visited:
return self.visited[word]
curr = self.Trie
res = float('-inf')
for i, w in enumerate(word):
if w not in curr:
return res
curr = curr[w]
if '#' in curr:
res = max(res, 1 + self.cntWords(word[i + 1:]))
self.visited[word] = res
return res
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
trie = Trie()
res = []
words.sort(key=len)
for word in words:
if trie.cntWords(word) >= 2:
res.append(word)
else:
trie.insert(word)
return res
```
### 相关题目
* [0208.implement-trie-prefix-tree](https://github.com/azl397985856/leetcode/blob/b8e8fa5f0554926efa9039495b25ed7fc158372a/problems/208.implement-trie-prefix-tree.md)
* [0211.add-and-search-word-data-structure-design](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/211.add-and-search-word-data-structure-design.md)
* [0212.word-search-ii](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/212.word-search-ii.md)
* [0820.short-encoding-of-words](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/820.short-encoding-of-words)
* [1032.stream-of-characters](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1032.stream-of-characters)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 