题目链接：472. 连接词
字典树，配合深度优先搜索。
在字典树中存储每一个字母，可能的后续字母，若可能为词的末尾，用 # 表示。
from typing import List
class Trie(object):
def __init__(self):
self.data = dict()
def insert(self, word):
data = self.data
for char in word:
if char not in data:
data[char] = dict()
data = data[char]
data['#'] = dict()
def query(self, word):
if len(word) == 0:
return True
data = self.data
for i, char in enumerate(word):
if char in data:
data = data[char]
else:
return False
if '#' in data and self.query(word[i + 1:]):
return True
return False
class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words = sorted(words, key=len)
trie, result = Trie(), list()
for word in words:
if len(word) == 0:
continue
if trie.query(word):
result.append(word)
else:
trie.insert(word)
return result