title
给定一个 不含重复 单词的字符串数组 words ，编写一个程序，返回 words 中的所有 连接词 。
连接词 的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
示例 1：
输入：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"组成。
示例 2：
输入：words = ["cat","dog","catdog"]
输出：["catdog"]
提示：
1 <= words.length <= 1040 <= words[i].length <= 1000words[i]仅由小写字母组成0 <= sum(words[i].length) <= 6 * 105
solution
https://github.com/azl397985856/leetcode/blob/master/problems/472.concatenated-words.md
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
trie = {}
for word in words:
node = trie
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = None
import functools
@functools.lru_cache(None)
def cutWord(word) -> int:
if not word: return 0
node = trie
res = float('-inf')
for i, c in enumerate(word):
if c not in node:
return res
node = node[c]
if "#" in node:
res = max(res, 1 + cutWord(word[i + 1:]))
return res
ans = []
for word in words:
if cutWord(word) >=2:
ans.append(word)
return ans