LeetCode 题解工作台
实现 Trie (前缀树)
Trie （发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。 请你实现 Trie 类： Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 …
4
题型
8
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
前缀树每个节点包括两部分： 1. 指向子节点的指针数组 ，对于本题而言，数组长度为 ，即小写英文字母的数量。 对应小写字母 ，...， 对应小写字母 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
解题思路
方法一：前缀树
前缀树每个节点包括两部分：
- 指向子节点的指针数组 ，对于本题而言，数组长度为 ，即小写英文字母的数量。 对应小写字母 ，...， 对应小写字母 。
- 布尔字段 ，表示该节点是否为字符串的结尾。
1. 插入字符串
我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
- 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
- 子节点不存在。创建一个新的子节点，记录在 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
2. 查找前缀
我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
- 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
- 子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 为真，则说明字典树中存在该字符串。
时间复杂度方面，插入字符串的时间复杂度为 ，查找前缀的时间复杂度为 ，其中 为字符串的长度，而 为字符集的大小（本题中为 ）。空间复杂度为 ，其中 为插入的字符串数量。
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, word: str) -> None:
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, word: str) -> bool:
node = self._search_prefix(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
node = self._search_prefix(prefix)
return node is not None
def _search_prefix(self, prefix: str):
node = self
for c in prefix:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return None
node = node.children[idx]
return node
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may ask about handling large alphabets efficiently with hash maps.
- question_mark
Expect questions on optimizing space with shared nodes or array-based children.
- question_mark
They often probe edge cases like empty strings or maximum-length words.
常见陷阱
外企场景- error
Forgetting to mark the end-of-word flag, causing search to fail on full words.
- error
Using arrays instead of hash maps in languages with sparse character sets, wasting space.
- error
Confusing prefix checks with full word checks, returning incorrect results for startsWith.
进阶变体
外企场景- arrow_right_alt
Implement a Trie that supports deletion of words while maintaining prefix correctness.
- arrow_right_alt
Extend the Trie to store frequencies or counts for autocomplete ranking.
- arrow_right_alt
Use a compressed Trie (Radix Tree) to reduce space for long strings with shared prefixes.