0X00 模板
创建 trie
trie = {}
for word in words:
p = trie
for idx, c in enumerate(word):
p = p.setdefault(c, {})
p['#'] = word
注意这里的 # 记录的是上一轮的单词
BFS
# BFS 遍历
from collections import deque
deq = deque([trie])
words = []
while deq:
n = deq.popleft()
if '#' in n:
words.append(n['#'])
for k, v in n.items():
if k != "#":
deq.append(v)
DFS
# 搜索所有单词
def dfs(node, words):
if '#' in node:
words.append(node['#'])
if len(node) == 1: return
for k, v in node.items():
if k != "#": dfs(v, words)
