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