LeetCode 208：实现 Trie（前缀树）—— Java 题解 ✅
🔗 题目链接
👉 https://leetcode.cn/problems/implement-trie-prefix-tree/
📖 内容概要
本文介绍如何使用 Java 实现一个 Trie（前缀树 / 字典树），支持以下三种操作：
- ✅ insert(word)：插入单词
- ✅ search(word)：查找完整单词
- ✅ startsWith(prefix)：查找前缀
代码已 AC（Accepted），结构清晰、易理解，适合面试与刷题使用。
💡 解题思路
什么是 Trie？
Trie 是一种 多叉树结构（26叉树），用于高效存储和检索字符串集合。
特点：
- 每个节点代表一个字符
- 从根节点到某一节点的路径构成一个字符串
- 用 end 标记是否为完整单词
数据结构设计
root
├── a
│ └── p
│ └── p
│ └── end = true ("app")
└── b
└── e
└── d
└── end = true ("bed")
核心思想
插入（insert）
- 从根节点开始
- 逐字符向下走
- 不存在则新建节点
- 最后一个字符标记为 end = true
查找（search）
- 沿路径向下
- 中途断掉 → 返回 false
- 到达末尾后，必须 end == true
前缀匹配（startsWith）
- 只要路径存在即可
- 不要求 end == true
✅ AC 代码（Java）
class Node {
Node[] children = new Node[26];
boolean end = false;
}
class Trie {
Node root;
public Trie() {
root = new Node();
}
// 插入单词
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
c -= 'a'; // 转为 0~25
if (cur.children[c] == null) {
cur.children[c] = new Node();
}
cur = cur.children[c];
}
cur.end = true;
}
// 查找完整单词
public boolean search(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
c -= 'a';
if (cur.children[c] == null) {
return false;
}
cur = cur.children[c];
}
return cur.end;
}
// 查找前缀
public boolean startsWith(String prefix) {
Node cur = root;
for (char c : prefix.toCharArray()) {
c -= 'a';
if (cur.children[c] == null) {
return false;
}
cur = cur.children[c];
}
return true;
}
}
⏱️ 复杂度分析
时间复杂度
| insert | O(L) |
| search | O(L) |
| startsWith | O(L) |
L 为字符串长度
空间复杂度
- 最坏情况：O(26^L)
- 实际远小于此值（共享前缀）
✅ 总结
- Trie 非常适合 前缀匹配、自动补全、词典查询
- 本题是 Trie 的入门模板题
- 掌握这一版代码，面试中 90% 的 Trie 问题都能直接套用
