前缀树模板

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)