复盘 · LC 208 实现 Trie (前缀树)

题目

题号：LeetCode 208
名称：实现 Trie (前缀树)（Implement Trie (Prefix Tree)）
难度：Medium
链接：leetcode.cn/problems/implement-trie-prefix-tree
今日代码：208-实现Trie(前缀树)/index.js

题意

实现前缀树 Trie，支持：

insert(word)：插入单词；
search(word)：单词是否存在（完整匹配）；
startsWith(prefix)：是否存在以该前缀开头的单词。
字符串只含小写英文字母。
多次插入、查询；空串边界按题意处理（一般不作为有效 word）。

涉及算法

标签	一句话
Trie	多叉树按字符分层；插入/查询都是沿边往下走
哈希嵌套	用 `{}` 或 `Map` 存「字符 → 子节点」

教程对照：本系列 23 · 字符串常考偏回文/前缀扫描；Trie 属「阶段 G」扩展结构，208 是入门实现题。

评价我的解法

你的思路：根节点 this.char 是嵌套对象，沿字符键往下建边；用 "-1" 标记单词结尾。三方法都实现了，逻辑能 AC。

我的代码（摘自 208-实现Trie(前缀树)/index.js，不含本地测例）：

javascript

var Trie = function () {
  this.char = {};
};

Trie.prototype.insert = function (word) {
  const charList = word.split("");
  let curCharList = this.char;
  for (const char of charList) {
    if (!curCharList[char]) {
      curCharList[char] = {};
    }
    curCharList = curCharList[char];
  }
  curCharList["-1"] = true;
};

Trie.prototype.search = function (word) {
  const charList = word.split("");
  let curCharList = this.char;
  for (const char of charList) {
    if (curCharList && char in curCharList) {
      curCharList = curCharList[char];
    } else {
      return false;
    }
  }
  if (curCharList["-1"]) {
    return true;
  }
  return false;
};

Trie.prototype.startsWith = function (prefix) {
  const charList = prefix.split("");
  let curCharList = this.char;
  for (const char of charList) {
    if (curCharList && char in curCharList) {
      curCharList = curCharList[char];
    } else {
      return false;
    }
  }
  return true;
};

对在哪、糙在哪：

结构正确：插入建链、查询沿链走、search 额外看结尾标记——和 Trie 定义一致。
"-1" 当结尾标记：可行；更常见是节点上 isEnd: true，避免和字母键命名空间混用（本题小写字母不会冲突，但面试口述时可提一嘴）。
search / startsWith 重复逻辑：前半段「沿前缀走」相同，可抽 walk(prefix) 返回末节点，search 再判 node.isEnd；现在分开写也能过，略啰嗦。
char in curCharList vs curCharList[char]：in 会扫原型链；纯 {} 节点没问题，若换 Object.create(null) 或 Map 更干净。
本地测例与注释：文件里留了 console.log 和注释掉的代码，提交前需删（和 994 同类坑）。
性能：LeetCode 显示用时/内存中等偏下；split("") 多一次数组分配，可直接 for (let i = 0; i < word.length; i++) 走字符。

小结：Trie 三操作都写对了，是合格实现；下一步统一节点结构（children + isEnd）、去掉调试代码，并默写「walk 一次、search/startsWith 复用」。

最佳题解

显式节点 + 共用 walk，语义清晰：

javascript

function TrieNode() {
  this.children = Object.create(null);
  this.isEnd = false;
}

var Trie = function () {
  this.root = new TrieNode();
};

Trie.prototype._walk = function (str) {
  let node = this.root;
  for (let i = 0; i < str.length; i++) {
    const c = str[i];
    if (!node.children[c]) return null;
    node = node.children[c];
  }
  return node;
};

Trie.prototype.insert = function (word) {
  let node = this.root;
  for (let i = 0; i < word.length; i++) {
    const c = word[i];
    if (!node.children[c]) node.children[c] = new TrieNode();
    node = node.children[c];
  }
  node.isEnd = true;
};

Trie.prototype.search = function (word) {
  const node = this._walk(word);
  return node !== null && node.isEnd;
};

Trie.prototype.startsWith = function (prefix) {
  return this._walk(prefix) !== null;
};

时间：插入 / 查询 / 前缀均为 O(m)，m 为字符串长度。
空间 O(总字符数 × 字母表)；为何更优：isEnd 与 children 分离，三方法共用 walk，面试好讲、换 211/212 也好扩。

关联题目

题	为何相关
211. 添加与搜索单词	Trie + 通配符 `.` 的 DFS
212. 单词搜索 II	Trie 存词典 + 网格 DFS
720. 词典中最长的单词	插入后按 Trie 判「可逐字构成」
14. 最长公共前缀	不用完整 Trie，但「按字符分层」同一直觉

一句话带走

Trie：每个节点是「字符 → 子节点」的映射，insert 走到尾打 isEnd，search 走完还要 isEnd，startsWith 走完即可。

复盘 · LC 208 实现 Trie (前缀树) ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​