01先把问题说具体
词典含 to、tea、ten。判断 te 是否为前缀,以及是否为完整单词,为什么需要不同答案?
02一步步得到方法
把字符串拆成逐字符决策
根代表空前缀,从根沿字符边前进,走过的路径拼成当前前缀。to、tea、ten 共享第一条 t 边;tea 与 ten 还共享 e 边,因此无需为每个词重复保存完整前缀。
节点需要终止标记。路径 te 存在只能证明某些单词以 te 开头;只有终止标记为真才表示 te 本身在词典中。空字符串若允许存入,则终止标记写在根上。
结构选择决定空间
每节点可用固定字母表数组,索引快但浪费空槽;也可用字典只保存存在的边。字典版适合字符集大而分支稀疏的情况,代价包含哈希与对象开销。
查询长度 m 的词最多走 m 条边,不依赖词典中其他词的长度。要列出一个前缀的所有补全,还要遍历对应子树并输出答案,成本不能只写 O(m)。
前缀存在与完整单词是两件事
插入 apple 会创建 a、ap、app 等前缀路径,但不意味着这些前缀都已作为完整单词插入。终止标记负责区分路径存在和单词结束,空字符串则对应根节点的终止标记。
删除时先取消单词结束标记,再决定哪些没有孩子且不再表示单词的节点可回收。不能因为删一个单词就把整条路径移除,否则会破坏共享前缀的其他单词。
03把一个小例子完全算清楚
插入 to、tea、ten,再查询 te。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 插入 to | 根→t→o,o 标记结束 | 创建两条边 |
| 插入 tea | 复用 t,新建 e、a | a 标记结束 |
| 插入 ten | 复用 t、e,新建 n | n 标记结束 |
| 查询 te | 路径到达 e,但 e 未结束 | 前缀 True,完整词 False |
窄屏可左右滑动表格,阅读完整计算与理由。
终止标记将单词集合与所有前缀集合区分开。
04为什么这个方法成立
- 每次插入沿已有边复用,不存在的边才新建,因此路径与字符前缀一一对应。
- 词尾终止标记恰好对应曾完整插入的字符串。
- 查询遇到缺边即可否定;走完后检查词尾标记即可判断完整成员。
05把推导翻译成代码
Python · 可独立运行的教学实现
class Trie:
def __init__(self):
self.root = {}
self.end = object()
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end] = True
def walk(self, text):
node = self.root
for char in text:
if char not in node:
return None
node = node[char]
return node
def contains(self, word):
node = self.walk(word)
return node is not None and self.end in node
def starts_with(self, prefix):
return self.walk(prefix) is not None逐个理解关键决定
self.end = object()- 独立哨兵不会与任何字符串字符冲突。
node is not None- 空字典也是合法节点,不能把真假值直接当路径是否存在。
06时间、空间与实现范围
插入、精确查询与前缀存在查询平均 O(m),m 为码点数。
节点数至多总字符数加根,字典节点开销可能显著;列举补全还需加访问和输出规模。
07改变条件,检查哪里会出错
节点存在就说明单词存在
必须检查终止标记。
删除单词时直接删除整条路径
会误删共享前缀;先去掉终止标记,再仅清理没有孩子且非词尾的节点。
忽略字符集与节点表示
固定大字母表数组可能浪费空间,字典更稀疏;复杂度要结合字符长度和边存储成本。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
再插入 te 后,tea 会消失吗?
需要一点提示
只增加终止标记。
查看解析与答案
不会。e 同时是词尾和更长词的前缀。
空前缀是否存在?
需要一点提示
它对应根。
查看解析与答案
存在,即使词典为空也有根;是否有任何补全则是另一个问题。
AC 自动机在 Trie 上补了什么?
需要一点提示
文本失配后如何复用后缀?
查看解析与答案
失败链接,使一次文本扫描能转向仍可能匹配的最长后缀前缀状态,下一专题会推导。