LeetCode 第 208 题：实现 Trie (前缀树)

题目描述
请你实现一个 Trie（前缀树）类，包含以下操作：

1. Trie() 初始化前缀树对象。
2. void insert(String word) 向前缀树中插入字符串 word。
3. boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，已在插入时存在）；否则，返回 false。
4. boolean startsWith(String prefix) 如果之前插入的字符串中存在以 prefix 为前缀的字符串，返回 true；否则，返回 false。

示例

输入：  
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]  
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]  
输出：  
[null, null, true, false, true, null, true]  

解题过程

1. 理解 Trie 树的结构
Trie 树是一种树形数据结构，用于高效存储和检索字符串集合中的键。每个节点包含以下部分：

• 子节点指针数组（例如，长度为 26，对应 26 个小写字母）。
• 布尔标记 isEnd，表示从根节点到当前节点的路径是否构成一个完整单词（即，该节点是某个单词的结尾）。

2. 设计 Trie 节点类
每个节点需要包含：

• 子节点数组 children，大小为 26（假设仅处理小写字母）。
• 布尔值 isEnd，标记单词结束。

3. 实现 Trie 类的基本框架

class TrieNode:  
    def __init__(self):  
        self.children = [None] * 26  # 26 个字母的指针  
        self.isEnd = False           # 标记单词结束  

class Trie:  
    def __init__(self):  
        self.root = TrieNode()        # 根节点不存储字符  

4. 实现插入操作 insert

• 从根节点开始，遍历单词的每个字符。
• 计算字符对应的索引（如 index = ord(ch) - ord('a')）。
• 若当前节点的 children[index] 为空，则新建节点。
• 移动指针到子节点，继续处理下一个字符。
• 遍历完成后，将当前节点的 isEnd 标记为 True。

示例步骤（插入 "apple"）：

1. 根节点 → 'a'（索引 0）：若空则创建节点，移动到该节点。
2. 当前节点 → 'p'（索引 15）：创建节点并移动。
3. 重复以上步骤，直到处理完 'e'。
4. 标记最后一个节点（'e'）的 isEnd = True。

5. 实现搜索操作 search

• 从根节点开始遍历单词的每个字符。
• 若遇到 children[index] 为空，说明单词不存在，返回 False。
• 遍历完成后，检查当前节点的 isEnd 是否为 True（确保是完整单词）。

6. 实现前缀查询 startsWith

• 过程与 search 类似，但无需检查 isEnd，只要路径存在即返回 True。

7. 完整代码实现

class TrieNode:  
    def __init__(self):  
        self.children = [None] * 26  
        self.isEnd = False  

class Trie:  
    def __init__(self):  
        self.root = TrieNode()  

    def insert(self, word: str) -> None:  
        node = self.root  
        for ch in word:  
            index = ord(ch) - ord('a')  
            if not node.children[index]:  
                node.children[index] = TrieNode()  
            node = node.children[index]  
        node.isEnd = True  

    def search(self, word: str) -> bool:  
        node = self.root  
        for ch in word:  
            index = ord(ch) - ord('a')  
            if not node.children[index]:  
                return False  
            node = node.children[index]  
        return node.isEnd  

    def startsWith(self, prefix: str) -> bool:  
        node = self.root  
        for ch in prefix:  
            index = ord(ch) - ord('a')  
            if not node.children[index]:  
                return False  
            node = node.children[index]  
        return True  

8. 复杂度分析

• 插入/查询时间：O(L)，其中 L 为单词或前缀的长度。
• 空间复杂度：最坏情况下需存储所有字符的节点，但通过共享前缀节省空间。

关键点总结

• Trie 树通过共享前缀优化存储和查询。
• isEnd 标记区分完整单词和前缀。
• 适用于前缀匹配、自动补全等场景。