# 0472. 连接词 ## 题目地址（472. 连接词） <https://leetcode-cn.com/problems/concatenated-words/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。 连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。 示例: 输入: ["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 即可 我们构造的前缀树大概是这样的：  问题的关键在于第二步中的**查找每一个单词有几个单词表中的单词组成**。 其实如果你了解前缀树的话应该不难写出来。 比如查找 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: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span> self.Trie = {} self.visited = {} <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, word)</span>:</span> curr = self.Trie <span class="hljs-keyword">for</span> w <span class="hljs-keyword">in</span> word: <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: curr[w] = {} curr = curr[w] curr[<span class="hljs-string">'#'</span>] = <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">cntWords</span><span class="hljs-params">(self, word)</span>:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> word: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> word <span class="hljs-keyword">in</span> self.visited: <span class="hljs-keyword">return</span> self.visited[word] curr = self.Trie res = float(<span class="hljs-string">'-inf'</span>) <span class="hljs-keyword">for</span> i, w <span class="hljs-keyword">in</span> enumerate(word): <span class="hljs-keyword">if</span> w <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> curr: <span class="hljs-keyword">return</span> res curr = curr[w] <span class="hljs-keyword">if</span> <span class="hljs-string">'#'</span> <span class="hljs-keyword">in</span> curr: res = max(res, <span class="hljs-params">1</span> + self.cntWords(word[i + <span class="hljs-params">1</span>:])) self.visited[word] = res <span class="hljs-keyword">return</span> res <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findAllConcatenatedWordsInADict</span><span class="hljs-params">(self, words: List[str])</span> -> List[str]:</span> self.trie = Trie() res = [] <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words: self.trie.insert(word) <span class="hljs-keyword">for</span> word <span class="hljs-keyword">in</span> words: <span class="hljs-keyword">if</span> self.trie.cntWords(word) >= <span class="hljs-params">2</span>: res.append(word) <span class="hljs-keyword">return</span> 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) - [1032.stream-of-characters](https://github.com/azl397985856/leetcode/blob/master/problems/1032.stream-of-characters.md) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。