208. 实现 Trie（前缀树）

题目描述

实现一个 Trie（前缀树），支持以下操作：

insert(word)：插入字符串 word。
search(word)：判断 word 是否完整地插入过。
startsWith(prefix)：判断是否存在以 prefix 开头的单词。

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

什么是 Trie？

Trie 是一棵专门存储字符串的树。每条边代表一个字符，从根节点出发的一条路径代表一个前缀。

例如依次插入 app、apple 和 apt：

(root)
   |
   a
   |
   p
  / \
 p*   t*
 |
 l
 |
 e*

* 表示“到这里可以组成一个完整单词”。三个单词共享了前缀 ap，所以 Trie 不需要重复保存这部分路径。

核心设计

一个 Trie 节点只需要保存两类信息：

children：从当前节点还能走向哪些字符。
isEnd：当前节点是否是某个完整单词的结尾。

这里最关键的是区分“前缀存在”和“完整单词存在”：

插入 apple 后，路径 a → p → p 已经存在，所以 startsWith("app") 为 true。
但 app 节点的 isEnd 仍是 false，所以 search("app") 为 false。
再插入 app 后，只需把该节点的 isEnd 改为 true，不需要创建新路径。

三个操作如何实现

插入单词

从根节点开始逐字符向下走：

对应的子节点不存在，就创建它。
移动到该子节点。
处理完所有字符后，将最后一个节点标记为单词结尾。

查找单词

先沿着单词的每个字符向下查找：

中途缺少节点，说明单词不存在。
路径存在，还必须检查最后节点的 isEnd；否则只能证明它是某个单词的前缀。

查找前缀

与查找单词几乎相同，但只要整条路径存在即可，不需要检查 isEnd。

因此可以抽取一个私有方法 findNode，返回字符串对应的最后节点；路径不存在时返回 null。

JavaScript 实现

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

Trie.prototype.insert = function (word) {
  let node = this;

  for (const char of word) {
    if (node.children[char] === undefined) {
      node.children[char] = new Trie();
    }
    node = node.children[char];
  }

  node.isEnd = true;
};

Trie.prototype.findNode = function (str) {
  let node = this;

  for (const char of str) {
    if (node.children[char] === undefined) {
      return null;
    }
    node = node.children[char];
  }

  return node;
};

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

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

使用 Object.create(null) 创建子节点表，是为了避免 constructor、toString 等原型属性与字符键发生干扰。题目限定字符为小写英文字母，使用普通对象也能通过；这里的写法更稳妥。

示例推演

执行 insert("apple")：

当前字符	操作	当前路径
`a`	创建节点	`a`
`p`	创建节点	`ap`
`p`	创建节点	`app`
`l`	创建节点	`appl`
`e`	创建节点并标记 `isEnd = true`	`apple`

随后执行不同查询：

查询	路径是否存在	末尾 `isEnd`	结果
`search("apple")`	是	`true`	`true`
`search("app")`	是	`false`	`false`
`startsWith("app")`	是	不需要检查	`true`
`search("ape")`	否	—	`false`

每一步生成的对象

为了方便观察，下面省略 JavaScript 中由 Object.create(null) 产生的原型信息，只展示 children 和 isEnd。

初始化 Trie：

{
  children: {},
  isEnd: false
}

读取字符 a，根节点下还没有 a，因此创建一个新节点：

{
  children: {
    a: {
      children: {},
      isEnd: false
    }
  },
  isEnd: false
}

读取第一个字符 p，在 a 节点下创建 p：

{
  children: {
    a: {
      children: {
        p: {
          children: {},
          isEnd: false
        }
      },
      isEnd: false
    }
  },
  isEnd: false
}

读取第二个字符 p，继续在当前 p 节点下创建新的 p：

{
  children: {
    a: {
      children: {
        p: {
          children: {
            p: {
              children: {},
              isEnd: false
            }
          },
          isEnd: false
        }
      },
      isEnd: false
    }
  },
  isEnd: false
}

读取字符 l，在第二个 p 节点下创建 l。为了避免后面的对象越来越宽，接下来使用单行路径表示嵌套的 children：

root.children.a.children.p.children.p.children.l = {
  children: {},
  isEnd: false
};

读取字符 e，在 l 节点下创建 e：

root.children.a.children.p.children.p.children.l.children.e = {
  children: {},
  isEnd: false
};

所有字符都处理完后，把 e 节点标记为完整单词的结尾：

root.children.a.children.p.children.p.children.l.children.e.isEnd = true;

最终对象可以简写为：

root
└── children.a
    └── children.p
        └── children.p
            └── children.l
                └── children.e
                    ├── children: {}
                    └── isEnd: true

注意，前面的 a、p、p、l 节点的 isEnd 都是 false。因此它们只是前缀；只有 apple 对应的 e 节点代表一个完整单词。

正确性说明

Trie 始终维护以下不变量：从根节点到任意节点的路径，恰好表示所有已插入单词中的一个前缀；节点的 isEnd 为 true，当且仅当这条路径本身是一个已插入的完整单词。

insert 为缺失字符创建节点，因此插入后整条单词路径一定存在；最后设置 isEnd，记录完整单词。
findNode 按字符逐层查找，因此只有目标路径完整存在时才会返回节点。
search 额外检查 isEnd，所以只匹配完整单词。
startsWith 只检查路径，所以正确匹配前缀。

复杂度分析

设本次操作的字符串长度为 m：

insert：时间复杂度 O(m)。
search：时间复杂度 O(m)。
startsWith：时间复杂度 O(m)。
空间复杂度：所有节点总数为 O(S)，其中 S 是所有已插入单词的字符总数。共享前缀会复用节点，因此实际节点数通常小于 S + 1。

不要把字符集大小 26 乘进时间复杂度：本实现通过字符键直接访问子节点，每个字符的查找平均是 O(1)。

易错点

只判断路径存在就认为单词存在：会把 apple 的前缀 app 错判为完整单词。
忘记在插入结束时设置 isEnd = true。
用同一个布尔条件实现 search 和 startsWith，忽略两者对 isEnd 的要求不同。
让辅助查找方法有时返回节点、有时返回 false，导致返回类型混乱；统一返回“节点或 null”更清晰。
误写复杂度。使用对象或 Map 存储子节点时，单次操作是 O(m)，不是 O(m × 26)。

面试时怎么说

可以用下面这段话快速说明思路：

Trie 把每个字符看作一层节点，共享相同前缀的单词会复用同一段路径。每个节点保存子节点和单词结束标记。插入时逐字符创建路径；查询时逐字符沿路径向下走。search 还要检查结束标记，startsWith 只需确认路径存在。三个操作的时间复杂度都是 O(m)。

延伸思考

如果字符集固定为 26 个小写字母，可以用长度为 26 的数组保存子节点；访问更直接，但每个节点都会预留 26 个位置，可能浪费空间。
使用对象或 Map 只保存实际存在的分支，通常更节省空间，也更容易扩展到更大的字符集。
Trie 还可以用于搜索建议、词频统计、自动补全，以及“是否存在某个前缀”等问题。

#208. 实现 Trie（前缀树）

#题目描述

#什么是 Trie？

#核心设计

#三个操作如何实现

#插入单词

#查找单词

#查找前缀

#JavaScript 实现

#示例推演

#每一步生成的对象

#正确性说明

#复杂度分析

#易错点

#面试时怎么说

#延伸思考