Trie 总结与复杂度分析
mediumTrie总结
Trie 时空复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 插入 | O(L) | L 为字符串长度 |
| 查找 | O(L) | — |
| 前缀查询 | O(P + 匹配数) | P 为前缀长度 |
| 删除 | O(L) | 需回溯 |
空间：最坏 O(TOTAL × alphabet)，TOTAL 为所有字符串总字符数。
Trie vs 其他数据结构
| 场景 | Trie | HashMap | 排序数组 |
|---|---|---|---|
| 精确查找 | O(L) | O(L) | O(L log n) |
| 前缀查询 | O(P) | O(n×L) | O(log n + k) |
| 词根替换 | O(L) | O(n×L) | — |
| 空间 | 高 | 中 | 低 |
| 顺序输出 | ✅ | ❌ | ✅ |
结论：需要前缀操作时 Trie 最优；仅需精确查找时 HashMap 更简单。
高频题型分类
前缀匹配类
- LC 208: 实现 Trie
- LC 211: 通配符搜索
- LC 648: 词根替换
- LC 1268: 搜索推荐系统
单词搜索类
- LC 79: 单词搜索（回溯）
- LC 212: 单词搜索 II（Trie+DFS）
统计/求和类
- LC 677: 键值映射前缀求和
- LC 642: 自动补全
位运算类
- LC 421: 最大异或值
常见模板
基础 Trie（数组形式，工业级推荐）
class Trie {
private int[][] children = new int[26 * MAX_WORDS][26];
private boolean[] isEnd = new boolean[26 * MAX_WORDS];
private int cnt = 1;
public void insert(String word) {
int node = 0;
for (char c : word.toCharArray()) {
int ci = c - 'a';
if (children[node][ci] == 0) children[node][ci] = cnt++;
node = children[node][ci];
}
isEnd[node] = true;
}
public boolean search(String word) {
int node = findNode(word);
return node != -1 && isEnd[node];
}
public boolean startsWith(String prefix) {
return findNode(prefix) != -1;
}
private int findNode(String s) {
int node = 0;
for (char c : s.toCharArray()) {
int ci = c - 'a';
if (children[node][ci] == 0) return -1;
node = children[node][ci];
}
return node;
}
}
位 Trie（最大 XOR）
// 建议掌握 insert + query 两个操作
// 从高位到低位遍历（31 ~ 0）
// query 时贪心选反向位
架构要点
- 何时用 Trie：题目有"前缀"、"词根"、"单词"相关词时优先考虑
- 节点设计：字符集 26 个用数组；Unicode 用 HashMap
- 结束标记：
isEnd布尔值，或存整个单词方便回溯 - 空间优化：压缩 Trie（Patricia Trie）合并无分叉路径