## 题目地址（472. 连接词）

https://leetcode-cn.com/problems/concatenated-words/

## 题目描述

```
给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["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。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。
```

## 思路

本题我的思路是直接使用前缀树来解决。**标准的前缀树模板**我在之前的题解中提到了，感兴趣的可以到下方的相关题目中查看。

这道题这里我们不需要 search，我们的做法是：

- 先进行一次遍历，将 words 全部插入（insert）到前缀树中。
- 然后再进行一次遍历，查找每一个单词有几个单词表中的单词组成
- 如果大于 2，则将其加入到 res 中
- 最后返回 res 即可

我们构造的前缀树大概是这样的：

![472.concatenated-words.png](http://ww1.sinaimg.cn/large/e9f490c8ly1gbkcox4r06j21eb15fgq8.jpg)

问题的关键在于第二步中的**查找每一个单词有几个单词表中的单词组成**。 其实如果你了解前缀树的话应该不难写出来。 比如查找 catsdogcats：

- 我们先从 c 到 a 到 t，发现 t 是单词结尾，我们数量 + 1
- 然后将剩下的部分“sdogcats”重新执行上述过程。
- s 发现找不到，我们返回 0
- 因此最终结果是 1

很明显这个逻辑是错误的，正确的划分应该是：

- 我们先从 c 到 a 到 t，再到 s，此时数量 + 1
- 然后将剩下的“dogcats”重复上述过程
- dog 找到了，数量 + 1
- 最后将 cats 加入。也找到了，数量再加 1

由于我们并不知道 cat 这里断开，结果更大？还是 cats 这里断开结果更大？因此我们的做法是将其全部递归求出，然后取出最大值即可。如果我们直接这样递归的话，可能会超时，卡在最后一个测试用例上。一个简单的方式是记忆化递归，从而避免重复计算，经测试这种方法能够通过。

## 代码

代码支持：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]:
        self.trie = Trie()
        res = []

        for word in words:
            self.trie.insert(word)
        for word in words:
            if self.trie.cntWords(word) >= 2:
                res.append(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://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)