0472. 连接词

题目地址（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 这里断开结果更大？因此我们的做法是将其全部递归求出，然后取出最大值即可。如果我们直接这样递归的话，可能会超时，卡在最后一个测试用例上。一个简单的方式是记忆化递归，从而避免重复计算，经测试这种方法能够通过。

2021-12-28 updated: 由于力扣增加了测试用例，导致了上面的仅仅依靠记忆化也是无法 AC 的。需要进一步优化。

我们可以将 words 排序，这样就可以剪枝了。如何剪枝呢？直接用代码比较直观：

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:

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