字典树
01 / 一句话本质
把一组字符串存储在一棵字符树上 — 每个节点代表一个前缀, 每条边代表一个字符,而一个特殊的词尾标记用来区分"该前缀本身就是一个已存储的单词" 与"这只是通向更长单词的一个前缀"。
题目在前缀树上存储与查找单词操作数7分布4 插入 · 3 查找
空字典树 — 只有根。每个操作都在树上一次走一个字符。
步
0 / 35
操作
—
节点数
1
上次结果
—
0 / 35
02 / 模式骨架
# 字典树节点 = 一个映射 + 一个"是否为词尾"标志class Node:children: dict[char, Node] = {}is_end: bool = False def insert(word):node = rootfor ch in word:if ch not in node.children:node.children[ch] = Node()node = node.children[ch]node.is_end = True def search(word):node = walk(word) # 逐字符走下去,未命中则返回 Nonereturn node is not None and node.is_end
03 / 什么时候用这个模式
"前缀查询"
问题关心的是前缀而非完整匹配 — 自动补全、最长公共前缀、"所有以 X 开头的单词"。 这类查询哈希集做不到优于线性扫描。
"单词词典"
一个固定的词典需要被反复查询。词典就是这棵字典树,查询则是树上的一次行走。 建树的代价摊销到每一次查询上。
"字母表有界的键"
每一步只在一组小而固定的取值中分支 — 小写字母(26)、数字(10)、IP 段(256)。 当字母表无界或连续时,应选择其他数据结构。
"共享结构"
像
"car"、"card"、"care"、"cart" 这样的单词共用前三个节点 — 字典树把这段前缀只存一次。 如果绝大多数单词都不共享前缀,字典树就只是哈希集的一个薄壳,优势大幅缩水。04 / 常见坑
i.
忘记词尾标记。
走到查询单词的最后一个字符还不够 — 该节点还必须被标记为
is_end。 省掉这一标记,在插入 "cat" 之后 search("ca") 也会返回成功, 这是错的。正是这个标记把前缀树变成了一个单词集合。ii.
混淆 search 与 startsWith。
search(w) 要求终点节点必须有词尾标记;startsWith(p) 只要求整次行走能走完 — 不检查词尾标记。底层走树的代码完全一样,后置条件只差一行。iii.
键空间不受限时还用 26 槽数组。
固定的
children[26] 数组对仅含小写字母的字母表既快又对缓存友好, 但用在更大的字母表(Unicode、字节流)上就是内存灾难。 默认用哈希表;只有当字母表很小且内层循环是热点时,才改回定长数组。05 / 去 LeetCode 上练习
家族中的四道题。第一道是经典的"实现数据结构"练习;接下来两道在其上增加特性(通配符、棋盘多串搜索); 第四道反过来:给定一个词典,找出具有特定结构性质的最长单词。