Implement Trie (Prefix Tree)（实现 Trie 前缀树）

题目 / Problem

中文： Trie（读音类似 “try”），也叫前缀树，是一种用于高效存储和检索字符串键的树形数据结构。常见应用包括自动补全、拼写检查和词典搜索。

实现 Trie 类：
Implement the Trie class:

Trie()：初始化前缀树对象。
Initializes the trie object.
void insert(String word)：将字符串 word 插入前缀树。
Inserts the string word into the trie.
boolean search(String word)：如果完整字符串 word 之前被插入过，返回 true；否则返回 false。
Returns true if the complete string word was previously inserted, and false otherwise.
boolean startsWith(String prefix)：如果存在已插入单词以 prefix 开头，返回 true；否则返回 false。
Returns true if any previously inserted word starts with prefix, and false otherwise.

English: A trie, pronounced “try,” or prefix tree, is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Applications include autocomplete and spell checking.

Trie 的结构 / Trie Structure

Trie 的每个节点表示一个字符位置。从根节点沿字符边向下走，形成一个前缀或完整单词。
Each trie node represents a character position. Following character edges from the root forms a prefix or a complete word.

例如，插入 "apple" 和 "app" 后：
After inserting "apple" and "app":

root
 └─ a
     └─ p
         └─ p  ← isEnd = true，表示 "app"
             └─ l
                 └─ e  ← isEnd = true，表示 "apple"

两个单词共享前缀 "app" 对应的节点路径，这正是 Trie 节省重复前缀存储并支持快速前缀查询的原因。
The two words share the nodes for prefix "app", allowing the trie to reuse prefixes and answer prefix queries efficiently.

节点设计 / Node Design

每个 TrieNode 包含：
Each TrieNode contains:

children：从当前节点出发的字符到子节点的映射。
children: a mapping from outgoing characters to child nodes.
isEnd：是否有一个完整单词在当前节点结束。
isEnd: whether a complete inserted word ends at this node.

根节点不代表任何字符，只作为所有单词路径的共同起点。
The root represents no character; it is the shared starting point for all word paths.

示例 / Example

Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:
[null, null, true, false, true, null, true]

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

第一次调用 search('app') 返回 false，因为 "app" 只是已插入单词 "apple" 的前缀，还没有作为完整单词插入。
The first search('app') returns false because "app" is only a prefix of the inserted word "apple"; it has not yet been inserted as a complete word.

startsWith('app') 返回 true，因为只要字符路径存在，就说明至少有一个已插入单词具有此前缀。
startsWith('app') returns true because the existing path proves that an inserted word has this prefix.

约束 / Constraints

1 <= word.length, prefix.length <= 2000
word 和 prefix 只包含小写英文字母。
word and prefix consist only of lowercase English letters.
对 insert、search 和 startsWith 的调用总数最多为 3 × 10⁴。
At most 3 × 10⁴ calls in total will be made to insert, search, and startsWith.

JavaScript 实现 / JavaScript Implementation

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  /**
   * @param {string} word
   * @return {void}
   */
  insert(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }

      node = node.children.get(char);
    }

    node.isEnd = true;
  }

  /**
   * @param {string} word
   * @return {boolean}
   */
  search(word) {
    const node = this.findNode(word);
    return node !== null && node.isEnd;
  }

  /**
   * @param {string} prefix
   * @return {boolean}
   */
  startsWith(prefix) {
    return this.findNode(prefix) !== null;
  }

  /**
   * @param {string} text
   * @return {TrieNode|null}
   */
  findNode(text) {
    let node = this.root;

    for (const char of text) {
      if (!node.children.has(char)) {
        return null;
      }

      node = node.children.get(char);
    }

    return node;
  }
}

search() 和 startsWith() 都需要沿字符路径查找，因此将共同逻辑提取到 findNode() 中。
Both search() and startsWith() follow a character path, so their shared traversal is extracted into findNode().

三种操作的区别 / Differences Between the Operations

`insert(word)`

逐字符沿树向下：
Walk down the trie character by character:

子节点不存在时，创建新节点。
Create a child when it does not exist.
子节点已存在时，复用现有节点。
Reuse the existing child when present.
最后将终点节点的 isEnd 设为 true。
Mark the final node's isEnd as true.

重复插入同一个单词不会破坏结构，只会再次将同一终点标记为 true。
Inserting the same word again does not damage the structure; it simply marks the same endpoint as true again.

`search(word)`

必须同时满足：
Both conditions must hold:

整条字符路径存在。
The complete character path exists.
最终节点的 isEnd === true。
The final node has isEnd === true.

路径存在只能说明它是某个单词的前缀，不能证明它作为完整单词插入过。
An existing path proves only that the text is a prefix; it does not prove that it was inserted as a complete word.

`startsWith(prefix)`

只需确认整条字符路径存在，不需要检查 isEnd。
Only the complete path must exist; isEnd is irrelevant.

执行过程 / Walkthrough

插入 `"apple"` / Insert `"apple"`

字符 / Character	当前操作 / Action
`a`	根节点下创建 `a` / Create `a` below root
`p`	在 `a` 下创建 `p` / Create `p` below `a`
`p`	在第一个 `p` 下创建第二个 `p` / Create the second `p`
`l`	创建 `l` / Create `l`
`e`	创建 `e`，并设置 `isEnd = true` / Create `e`; set `isEnd = true`

查询 `search("app")` / Search for `"app"`

路径 root → a → p → p 存在，但最后节点的 isEnd 是 false，因此返回 false。
The path root → a → p → p exists, but its final node has isEnd === false, so return false.

查询 `startsWith("app")` / Check Prefix `"app"`

相同路径存在，前缀查询不检查 isEnd，因此返回 true。
The same path exists, and prefix lookup does not inspect isEnd, so return true.

插入 `"app"` 后再次查询 / Search After Inserting `"app"`

插入时复用现有的 a → p → p 路径，并将最后一个 p 的 isEnd 设置为 true。之后 search("app") 返回 true。
Insertion reuses the existing a → p → p path and marks the final p as an endpoint. A later search("app") returns true.

复杂度 / Complexity

设操作字符串的长度为 L。
Let L be the length of the word or prefix used by an operation.

操作 / Operation	时间 / Time	额外空间 / Additional Space
`insert`	`O(L)`	最坏 `O(L)`，创建新节点 / Up to `O(L)` new nodes
`search`	`O(L)`	`O(1)`
`startsWith`	`O(L)`	`O(1)`

如果所有插入单词的总字符数为 C，Trie 的总空间复杂度最坏为 O(C)。共享前缀会复用节点，因此实际节点数可能更少。
If all inserted words contain C characters in total, the trie's worst-case space is O(C). Shared prefixes reuse nodes, so the actual node count may be smaller.

使用固定 26 位数组 / Using a Fixed 26-Element Array

因为字符只包含小写英文字母，也可以让每个节点使用长度为 26 的数组保存子节点：
Because inputs contain only lowercase English letters, each node can instead use a fixed array of 26 children:

class ArrayTrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEnd = false;
  }
}

字符下标可以通过以下方式获得：
Obtain a character index with:

const index = char.charCodeAt(0) - 'a'.charCodeAt(0);

结构 / Structure	优点 / Advantage	缺点 / Disadvantage
`Map`	只保存实际存在的子节点，代码直观 / Stores only existing children	哈希结构有额外开销 / Hashing overhead
长度 26 的数组	访问下标直接，通常更快 / Direct indexed access	每个节点固定分配 26 个位置 / Allocates 26 slots per node

本题中两种方式都可以。Map 实现更容易阅读，并能自然扩展到更大的字符集。
Either representation works here. Map is easier to read and naturally extends to larger character sets.

易错点 / Common Pitfalls

search() 必须检查 isEnd，不能只检查路径是否存在。
search() must inspect isEnd, not merely path existence.
startsWith() 只检查路径，不要求最终节点是单词结尾。
startsWith() checks only the path; the final node need not end a word.
插入单词结束后不要忘记设置 isEnd = true。
Set isEnd = true after inserting the complete word.
多个单词可能共享前缀，应复用已经存在的节点。
Multiple words may share a prefix, so reuse existing nodes.
根节点不代表任何字符。
The root node represents no character.
不能用“节点没有子节点”判断单词结束，因为一个完整单词也可能是另一个单词的前缀。
Do not identify word endings by the absence of children; a complete word may also be a prefix of another word.

Implement Trie (Prefix Tree)