LeetCode 208. 实现 Trie (前缀树)
目录
题目描述
题意分析
要实现一个数据结构，对外暴露三个操作：
insert(word)把一个单词存进去，search(word)回答「这个单词被完整插入过吗」，startsWith(prefix)回答「有没有任何已插入的单词以它开头」。这三个操作里，后两个的语义差别是全题的重心：
search("app")问的是app本身是不是一个被插入过的单词；startsWith("app")只问有没有单词把app当作开头，哪怕库里只有apple，答案也是 true。反过来，insert("apple")之后search("app")必须是 false —— 走得通路不等于走到了终点。约束里最强的信号是「所有输入只含小写英文字母」。字符集固定为 26 个，意味着每个节点的分支数是常数，可以直接用定长数组按
c - 'a'下标寻址，不必用哈希表。另一个信号是调用次数可达 $3 \times 10^4$、单串长度可达 2000，所以每次操作必须做到与串长同阶，不能每次去遍历已插入的全部单词。边界上要留意：同一个单词可能被重复插入；一个单词可能是另一个单词的前缀（
app与apple同时存在）；查询的串可能压根没被插入过，此时要在中途就能判定失败。题目保证输入非空，不必处理空串。
解法：数组孩子节点实现 Trie
核心思路
问题关键：
search与startsWith都要判断一段字符路径是否存在，但前者还要求该路径恰好是一个已插入单词。只存字符串集合会让前缀查询反复扫描所有单词，也无法复用公共前缀。为什么选 Trie：把每个单词按字符拆成从根出发的路径，
apple与apply的公共前缀只保存一次。题目限定为 26 个小写字母，孩子节点用长度为 26 的数组即可通过c - 'a'直接定位，比哈希表更简单。不变量：从根走到任意节点的路径唯一表示一个前缀；节点的
isEnd仅表示“有单词恰好在这里结束”。因此，路径存在不代表完整单词存在。插入时沿字符路径前进，缺节点才创建，最后标记
isEnd。查询时只读地走同一条路径：中途断开返回null；startsWith只检查节点是否存在，search再检查isEnd。正确性：插入一个单词后，按其字符一定能走到对应终点；只有完整插入结束时才会设置
isEnd，所以search为真当且仅当该单词被插入过。任意已插入单词的每个前缀都位于其路径上，所以startsWith为真当且仅当存在该前缀。
解题步骤
- 根节点表示空前缀，每个节点保存 26 个孩子和一个终点标记。
insert逐字符计算下标；孩子不存在就创建，存在则复用；走完后设置isEnd = true。- 用
searchPrefix统一完成路径查找，遇到空孩子立即失败，整个过程不修改 Trie。search判断“路径存在且终点标记为真”，startsWith只判断“路径存在”。面试口述示例：插入
apple后，app的路径已经存在，但对应节点的isEnd仍是false，所以search("app")为false，startsWith("app")为true。再插入app后，只需把该节点标成终点，两个查询都为true。边界反例：重复插入同一单词只是重复设置布尔值，不影响结果；查询
apply会在y处断路，不能在查询时顺手创建节点，否则会污染后续前缀判断。
代码实现
class Trie {
private final TrieNode root = new TrieNode();
public Trie() {
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private TrieNode searchPrefix(String text) {
TrieNode node = root;
for (int i = 0; i < text.length(); i++) {
node = node.children[text.charAt(i) - 'a'];
if (node == null) {
return null;
}
}
return node;
}
private static class TrieNode {
private final TrieNode[] children = new TrieNode[26];
private boolean isEnd;
}
}
type Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for i := 0; i < len(word); i++ {
index := word[i] - 'a'
if node.children[index] == nil {
node.children[index] = &Trie{}
}
node = node.children[index]
}
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 {
return this.searchPrefix(prefix) != nil
}
func (this *Trie) searchPrefix(text string) *Trie {
node := this
for i := 0; i < len(text); i++ {
node = node.children[text[i]-'a']
if node == nil {
return nil
}
}
return node
}
复杂度分析
- 时间复杂度：三种操作均为 $O(L)$，其中 $L$ 是本次传入字符串的长度；每个字符只做一次数组寻址。
- 空间复杂度：$O(T)$，其中 $T$ 是所有插入过程中实际创建的节点数，最坏为所有单词长度之和。每个节点的 26 个孩子槽位是固定常数。
关键点总结
- Trie 用路径表示前缀，公共前缀只存一份，操作耗时只与当前字符串长度有关。
- “路径可达”和“完整单词”必须分开；
isEnd不能由“是否有孩子”替代。- 插入负责创建节点，查询必须只读；三个接口共用同一个路径查找函数。
- 字符集固定且很小时用数组；若字符集很大或稀疏，再把孩子结构换成哈希表。
易错点总结
search只判断路径存在：插入apple后会把未插入的app误判为单词，必须再检查isEnd。startsWith也检查isEnd：同一用例会把合法前缀app判为不存在。- 忘记在插入结束处设置
isEnd：路径虽然完整，search("apple")仍会返回false。- 查询时创建缺失节点：先查
xyz再查前缀x会凭空得到true。- 用“节点没有孩子”表示单词结束：同时插入
app和apple时，app有孩子但仍是完整单词。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 062. 实现 Trie (前缀树) | 中等 | 同题换皮，可直接套用 26 叉数组加 isEnd 的实现 |
| 211. 添加与搜索单词 - 数据结构设计 | 中等 | 查询串含通配符 .，节点处需对 26 个孩子分支递归而非单路下行 |
| 677. 键值映射 | 中等 | 节点存的不是布尔标记而是权值，前缀查询要累加子树和 |
| 648. 单词替换 | 中等 | 把词典建成 Trie 后对句子逐词匹配最短前缀，考的是提前停在 isEnd
|
| 212. 单词搜索 II | 困难 | Trie 与网格 DFS 结合，用树上路径做剪枝并在命中后摘除节点去重 |
| 588. 设计内存文件系统 | 困难 | 边上是路径分段而非单字符，节点还要区分目录与文件并支持排序列举 |