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 即可
我们构造的前缀树大概是这样的：
问题的关键在于第二步中的查找每一个单词有几个单词表中的单词组成。 其实如果你了解前缀树的话应该不难写出来。 比如查找 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:
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- 前缀树