LeetCode LCR 062. 实现 Trie (前缀树)
目录
题目描述
题意分析
设计一个字符串集合，支持三种操作：插入一个单词、查询某个单词是否被完整插入过、查询是否存在以某个字符串为前缀的已插入单词。三个接口都要高效。
关键在于
search与startsWith的语义差别。insert("apple")之后，search("app")必须返回false，因为"app"从未作为完整单词插入；而startsWith("app")必须返回true，因为"apple"以它开头。这说明数据结构除了要能沿着字符走下去，还必须能区分「这里只是路过」和「这里是某个单词的终点」。约束给出的信号很明确：所有字符串只含小写英文字母，字符集固定为 26；调用总次数到 $3 \times 10^4$，单串长度到 2000。字符集小而固定，意味着每个节点用一个长度 26 的数组做转移表是划算的，查找转移是 $O(1)$ 且没有哈希开销；总字符量有上界，意味着按字符逐位下沉的做法总代价可控。
边界上要注意：查询的字符串可能在集合中根本没有对应路径，中途就断掉；插入同一个单词多次应当幂等；前缀查询允许查询串正好等于某个已插入单词，此时也算前缀成立。
解法：哈希表统计状态
核心思路
最朴素的实现是把所有单词丢进一个哈希集合。
insert和search都是 $O(L)$，非常好；但startsWith只能遍历集合里每个单词逐个比对前缀，代价是 $O(N \cdot L)$，在 $3 \times 10^4$ 次调用下彻底崩掉。瓶颈在于哈希把整个单词压成一个不可分解的键，前缀信息在哈希的那一刻就被销毁了。而前缀查询本质上需要「共享开头的单词能被一起处理」，这要求结构保留字符串的逐字符层次。
观察到：所有以
"app"开头的单词，它们的前三个字符走的是同一条路径。把字符串看成一条从根出发的路径、每个字符是一条边，那么「拥有公共前缀」就等价于「共享一段起始路径」。于是集合被组织成一棵树，根代表空串，从根走到任意节点的路径拼起来就是一个前缀。由此定下节点的状态定义：每个节点持有
children[26]，children[c]非空表示「当前前缀后面接字符c仍然是某个已插入单词的前缀」；另有布尔位isEnd，表示「从根到当前节点这条路径本身是一个完整单词」。这两项就是全部状态，search与startsWith的差别被完全收敛到isEnd上。维持的不变量是：根到任一存在节点的路径，一定是某个已插入单词的前缀；且
isEnd为真当且仅当该路径是一个被完整插入过的单词。有了它，三个接口都变成同一个动作——沿字符下沉，走不通即失败——只是终点处的判定条件不同。
解题步骤
- 节点结构定义为「26 叉指针数组 + 一个结束标记」。用定长数组而不是哈希表，是因为字符集固定为 26，数组下标
c - 'a'直接寻址，常数远小于哈希，且不必处理扩容。insert从根出发逐字符下沉：若对应子节点为空则新建，然后移动到该子节点。新建是「按需」的，只有真正出现过的前缀才占用节点，这保证空间与总字符量同阶而不是 $26^L$。insert走完全部字符后，把终点节点的isEnd置为真。置位而不是计数，使得重复插入同一单词天然幂等。- 把
search与startsWith的公共部分抽成私有的searchPrefix：沿字符下沉，中途遇到空子节点立刻返回空，走完返回终点节点。抽出来是因为两者的寻路逻辑完全一致，差别仅在终点如何判定，合并可以杜绝两份代码走偏。startsWith只需判断searchPrefix的返回值非空——路径存在就说明存在以它为前缀的单词。search在非空的基础上还要检查isEnd——路径存在只说明是前缀，必须终点标记为真才算完整单词。这一处判定是整题唯一的区分点，漏掉它两个接口就退化成同一个。以调用序列
insert("apple")→search("apple")→search("app")→startsWith("app")→insert("app")→search("app")走一遍：insert("apple")从根开始，a、p、p、l、e五个子节点依次因为为空而被新建，最后e所在节点的isEnd置真，此时树上共 5 个非根节点，只有最后一个isEnd为真。search("apple")沿a→p→p→l→e五步全部走通，终点非空且isEnd为真，返回true。search("app")沿a→p→p三步走通，终点非空但isEnd为假（它只是"apple"路上的中转），返回false。startsWith("app")走到同一个节点，只要求非空，返回true。insert("app")再走一遍a→p→p，三个子节点都已存在故不新建，只把该节点的isEnd置真。此后search("app")终点非空且isEnd为真，返回true——整棵树的节点数依旧是 5，唯一的变化是多了一个结束标记。
代码实现
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
}
public void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String s) {
Trie node = this;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
return null;
}
node = node.children[idx];
}
return node;
}
}
type Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (this *Trie) Search(word string) bool {
node := this.SearchPrefix(word)
return node != nil && node.isEnd
}
func (this *Trie) StartsWith(prefix string) bool {
node := this.SearchPrefix(prefix)
return node != nil
}
func (this *Trie) SearchPrefix(s string) *Trie {
node := this
for _, c := range s {
idx := c - 'a'
if node.children[idx] == nil {
return nil
}
node = node.children[idx]
}
return node
}
复杂度分析
- 时间复杂度：三个接口都是 $O(L)$，$L$ 为传入字符串的长度。每个字符只做一次常数级的数组下标寻址，与已插入单词的数量完全无关。
- 空间复杂度：$O(26 \cdot C)$，$C$ 为所有插入单词去掉公共前缀后的节点总数，上界是全部插入字符数。每个节点固定携带一个长度 26 的指针数组，公共前缀被复用因而不重复计费。
关键点总结
- 前缀查询要求结构保留字符的层次关系，哈希集合把单词压成整体键、销毁了前缀信息，这是选择树形结构的根本理由。
isEnd是把「路径存在」和「单词存在」区分开的唯一手段。设计时先明确每个状态位回答哪个问题，接口实现自然就分岔清楚了。- 字符集固定且小时用定长数组做转移表，寻址 $O(1)$ 且无哈希常数；字符集大或稀疏时才换成哈希映射，这是一个可迁移的取舍标准。
search与startsWith共享寻路逻辑，抽出公共私有方法既省代码也防止两者行为漂移，是设计类题目里稳拿印象分的写法。- 节点按需创建，空间只与实际出现的前缀相关；公共前缀天然共享，这正是 Trie 相比逐串存储的空间优势所在。
- 面试视角：白板上先画出插入
"apple"和"app"之后的树形，用图指出哪个节点isEnd为真，比直接写代码更容易让面试官确认你理解了语义差别。- 面试视角：常见追问是「如何支持删除」和「如何支持通配符匹配」。前者答给节点加引用计数、删除时逐层减一并回收计数归零的节点；后者答在
.处对 26 个子节点递归分支，正是 211 题的做法。
易错点总结
- 错误写法：
search只判断路径是否走通，不检查isEnd。用例insert("apple")后search("app")→ 路径走得通于是返回true，正确答案是false，search退化成了startsWith。- 错误写法：
startsWith也顺手检查了isEnd。用例insert("apple")后startsWith("app")→ 终点isEnd为假于是返回false，正确答案是true。- 错误写法：
insert在下沉过程中给每个途经节点都置isEnd为真。用例insert("apple")后search("app")→ 返回true，正确答案是false，所有前缀都被误标成了完整单词。- 错误写法：
searchPrefix中途遇到空子节点仍继续循环。用例insert("apple")后search("apq")→ 第三个字符处子节点为空，不立即返回则下一轮解引用空指针抛异常。- 错误写法：
insert时把已存在的子节点也重新new一遍覆盖掉。用例insert("apple")后insert("apply")再search("apple")→ 第二次插入把共享的a→p→p→l路径重建成空节点，先前的"apple"终点标记丢失，返回false。- 错误写法：把
isEnd换成「该节点无任何子节点即为单词结尾」的判断。用例insert("apple")、insert("app")后search("app")→app节点还有子节点l，判定为非结尾返回false，正确答案是true。- 错误写法：下标计算写成
c - 'A'。用例insert("a")→'a' - 'A'等于 32，越过长度 26 的数组抛越界异常。- 错误写法：Go 版本把
Insert的接收者写成值接收者func (this Trie)。用例insert("a")后search("a")→ 值接收者操作的是结构体副本，isEnd的修改写在副本上，原对象毫无变化，返回false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 208. 实现 Trie (前缀树) | 中等 | 与本题同题，可用来对比数组转移表与哈希转移表的常数差异 |
| 211. 添加与搜索单词 - 数据结构设计 | 中等 | 查询串含通配符 .，寻路从单链下沉变成 26 路递归分支 |
| 212. 单词搜索 II | 困难 | Trie 只作剪枝索引，主体是网格回溯，命中后还要处理去重与剪枝 |
| 648. 单词替换 | 中等 | 需要在下沉途中提前停在最短词根，考的是遍历中途的终止时机 |
| 677. 键值映射 | 中等 | 节点上挂的是可累加的权值而非布尔位，插入需处理同键覆盖更新 |
| 720. 词典中最长的单词 | 中等 | 要求路径上每个前缀都是完整单词，判定落在整条路径而不只是终点 |
| 1268. 搜索推荐系统 | 中等 | 每个前缀要返回字典序最小的三个结果，节点需额外维护候选列表 |