.jpg)
689 字
3 分钟
实现 Trie (前缀树)
.png)
题目描述
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
解题思路
- 树节点设计：
- 每个节点包含：
children数组/映射（长度26，对应26字母）isEnd标记（是否为单词结尾）
- 每个节点包含：
- 核心操作：
- 插入：遍历单词字符，逐层创建节点，结尾标记
isEnd=true - 搜索：遍历路径存在且结尾
isEnd=true - 前缀搜索：只需路径存在（不要求结尾标记）
- 插入：遍历单词字符，逐层创建节点，结尾标记
- 字符映射：
charCodeAt() - 97将字符映射到 0-25 索引- 或使用
Map实现动态映射
关键洞察
- 前缀共享原理：
- 相同前缀的单词共享节点路径（如 “app” 和 “apple” 共享 “a-p-p”）
- 结尾标记必要性：
isEnd区分完整单词和中间路径（如 “app” 存在但 “apple” 未完成）
- 路径即存储：
- 单词不显式存储，由根节点到
isEnd节点的路径表示
- 单词不显式存储，由根节点到
- 动态扩展性：
- 插入时按需创建节点，避免预分配空间浪费
- 搜索优化：
- 前缀搜索比遍历字典快 O(m)（m为前缀长度）
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 插入 | O(m) | O(m) |
| 搜索单词 | O(m) | O(1) |
| 搜索前缀 | O(m) | O(1) |
注：
- m 为单词/前缀长度
- 空间复杂度：
- 最坏情况 O(26×M)，M 为所有单词总字符数
- 实际共享前缀后远小于 M
代码实现
const END = Symbol('end');
var Trie = function() { this.root = Object.create(null);};
Trie.prototype.insert = function(word) { let node = this.root; for (const ch of word) { node = node[ch] || (node[ch] = Object.create(null)); } node[END] = true;};
Trie.prototype.search = function(word) { const node = this.traverse(word); return !!(node && node[END]);};
Trie.prototype.startsWith = function(prefix) { return !!this.traverse(prefix);};
Trie.prototype.traverse = function(prefix) { let node = this.root; for (const ch of prefix) { if (!node[ch]) return null; node = node[ch]; } return node;};实际应用场景
- 输入法预测：根据前缀推荐候选词`
- 搜索建议：搜索引擎的自动补全`
- 路由转发：IP 路由最长前缀匹配`
- 拼写检查：词典快速检索`