LeetCode 208. 实现 Trie（前缀树）
题目核心
实现一个前缀树 Trie，支持三个操作：
insert(word)：插入一个单词。search(word)：判断完整单词是否存在。startsWith(prefix)：判断是否存在以指定前缀开头的单词。
Trie 会把具有相同前缀的单词共享在同一条路径上。例如插入 apple 和 app 后，它们会共享 a -> p -> p 这段路径。
解题思考过程
第一步：理解问题
Trie（前缀树）是一种专门为字符串前缀匹配设计的数据结构。
为什么需要 Trie？
如果用哈希表存储单词：
- search: O(1) - 很快
- startsWith: O(n) - 需要遍历所有单词检查前缀，太慢
如果用 Trie：
- search: O(k) - k是单词长度
- startsWith: O(k) - k是前缀长度Trie 的优势在于前缀匹配效率高。
第二步：设计节点结构
每个节点需要什么信息？
1. 子节点：用对象存储，key是字符，value是子节点
2. 是否是单词结尾：用 isEnd 标记
例如：
插入 "app" 和 "apple"
根节点
└── a
└── p
└── p (isEnd=true)
└── l
└── e (isEnd=true)第三步：实现 insert 方法
插入单词时，从根节点开始，逐个字符创建节点：
insert("apple"):
1. 根节点 -> a（创建）
2. a -> p（创建）
3. p -> p（创建）
4. p -> l（创建）
5. l -> e（创建，isEnd=true）
insert("app"):
1. 根节点 -> a（已存在）
2. a -> p（已存在）
3. p -> p（已存在，设置 isEnd=true）第四步：实现 search 方法
查找单词时，从根节点开始，逐个字符匹配：
search("app"):
1. 根节点 -> a（存在）
2. a -> p（存在）
3. p -> p（存在，isEnd=true）
返回 true ✓
search("apps"):
1. 根节点 -> a（存在）
2. a -> p（存在）
3. p -> p（存在）
4. p -> s（不存在）
返回 false ✗
search("ap"):
1. 根节点 -> a（存在）
2. a -> p（存在，isEnd=false）
返回 false ✗（不是完整单词）第五步：实现 startsWith 方法
前缀匹配和 search 类似，但不需要检查 isEnd：
startsWith("ap"):
1. 根节点 -> a（存在）
2. a -> p（存在）
返回 true ✓（不管后面有没有，只要前缀匹配就可以）第六步：时间复杂度分析
insert: O(k) - k是单词长度
search: O(k) - k是单词长度
startsWith: O(k) - k是前缀长度空间复杂度：O(n*k)，n是单词数量，k是平均长度。
节点结构
每个 Trie 节点需要保存两类信息：
var Trie = function () {
this.children = {};
this.isEnd = false;
};children：从当前节点出发的字符分支，键是字符，值是下一个 Trie 节点。isEnd：是否有一个完整单词在当前节点结束。
isEnd 非常重要，因为 app 可能只是 apple 的前缀，也可能本身就是一个已经插入的单词。
当前代码需要修正的地方
当前代码的 insert 中，读取子节点和写入子节点使用了不同路径：
if (!current.children[char]) {
current[char] = new Trie();
}
current = current.children[char];新节点被写入了 current[char]，但随后读取的是 current.children[char]。因此第一次插入新字符时，current.children[char] 仍然是 undefined，代码无法正常完成插入。
写入位置应改为：
current.children[char] = new Trie();下面的讲解基于修正后的实现。
插入单词
从根节点开始依次处理单词中的字符。如果对应分支不存在，就创建新节点；最后把结束节点标记为完整单词的结尾。
Trie.prototype.insert = function (word) {
let current = this;
for (const char of word) {
if (!current.children[char]) {
current.children[char] = new Trie();
}
current = current.children[char];
}
current.isEnd = true;
};插入代码逐行解释
Trie.prototype.insert = function (word) {定义插入方法，参数 word 是要插入的单词。
let current = this;current 指向当前节点，初始为根节点（this）。
for (const char of word) {遍历单词中的每个字符。
if (!current.children[char]) {
current.children[char] = new Trie();
}如果当前节点的 children 中没有该字符对应的节点，就创建一个新的 Trie 节点。
current = current.children[char];移动到下一个节点，继续处理下一个字符。
}
current.isEnd = true;
};遍历完所有字符后，将当前节点的 isEnd 标记为 true，表示这是一个完整单词的结尾。
插入过程示例
插入 apple 后，结构可以理解为：
root
└─ a
└─ p
└─ p
└─ l
└─ e (isEnd = true)再插入 app：
root
└─ a
└─ p
└─ p (isEnd = true)
└─ l
└─ e (isEnd = true)app 和 apple 共享了 a -> p -> p 路径，只是在第二个 p 处标记了 isEnd = true。
搜索完整单词
搜索时沿着每个字符对应的分支向下走。任何一个字符不存在，都可以立即返回 false。
Trie.prototype.search = function (word) {
let current = this;
for (const char of word) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return current.isEnd;
};搜索代码逐行解释
Trie.prototype.search = function (word) {定义搜索方法，参数 word 是要搜索的完整单词。
let current = this;从根节点开始。
for (const char of word) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}遍历单词中的每个字符。如果某个字符对应的分支不存在，说明单词不存在，返回 false。否则继续向下走。
return current.isEnd;
};走完所有字符后，必须检查 isEnd。例如只插入了 apple 时，搜索 app 能走完路径，但 app 对应节点的 isEnd 仍为 false，所以它还不是一个完整单词。
搜索前缀
前缀搜索不要求路径终点是完整单词，因此只要所有字符都能找到即可：
Trie.prototype.startsWith = function (prefix) {
let current = this;
for (const char of prefix) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return true;
};前缀搜索代码逐行解释
Trie.prototype.startsWith = function (prefix) {定义前缀搜索方法，参数 prefix 是要搜索的前缀。
let current = this;从根节点开始。
for (const char of prefix) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}遍历前缀中的每个字符。如果某个字符对应的分支不存在，说明没有以该前缀开头的单词，返回 false。
return true;
};走完所有字符后，直接返回 true，不需要检查 isEnd。因为前缀搜索只关心是否存在以该前缀开头的单词，不关心前缀本身是否是完整单词。
search 和 startsWith 的区别
search 和 startsWith 的唯一区别，就是走完路径后是否需要检查 isEnd：
search：检查isEnd，确保路径终点是一个完整单词。startsWith：不检查isEnd，只要路径存在即可。
完整修正版
var Trie = function () {
this.children = {};
this.isEnd = false;
};
Trie.prototype.insert = function (word) {
let current = this;
for (const char of word) {
if (!current.children[char]) {
current.children[char] = new Trie();
}
current = current.children[char];
}
current.isEnd = true;
};
Trie.prototype.search = function (word) {
let current = this;
for (const char of word) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return current.isEnd;
};
Trie.prototype.startsWith = function (prefix) {
let current = this;
for (const char of prefix) {
if (!current.children[char]) {
return false;
}
current = current.children[char];
}
return true;
};复杂度
设传入字符串长度为 L：
insert时间复杂度：O(L)。search时间复杂度：O(L)。startsWith时间复杂度：O(L)。- 空间复杂度：最坏为
O(L)，发生在插入的字符全部需要创建新节点时。
整个 Trie 的总空间取决于所有不重复前缀的数量。共享前缀越多，相比单独存储每个单词越节省空间。
为什么要用 Trie
Trie 的优势在于前缀匹配：
- 前缀搜索效率高：查找前缀的时间复杂度只与前缀长度有关，与字典中的单词数量无关。
- 前缀共享：具有相同前缀的单词共享路径，节省存储空间。
- 自动补全：从某个节点出发，可以遍历所有以该前缀开头的单词。
使用示例
const 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执行过程：
插入 "apple"：
root -> a -> p -> p -> l -> e (isEnd = true)
搜索 "apple"：
root -> a -> p -> p -> l -> e，isEnd = true → 返回 true
搜索 "app"：
root -> a -> p -> p，isEnd = false → 返回 false
前缀搜索 "app"：
root -> a -> p -> p，路径存在 → 返回 true
插入 "app"：
root -> a -> p -> p (isEnd = true) -> l -> e (isEnd = true)
搜索 "app"：
root -> a -> p -> p，isEnd = true → 返回 true