好的，我们这次来详细讲解 LeetCode 第 208 题：实现 Trie (前缀树)。

这道题是学习数据结构，特别是字符串处理中一个非常重要的基础。它不像一些算法题那样有复杂的逻辑推导，但理解并实现它能极大地提升你对高效字符串检索的认识。

1. 题目描述

题目：实现一个 Trie (前缀树)，包含 insert, search 和 startsWith 这三个操作。

示例：

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

说明:

• 你可以假设所有的输入都是由小写字母 a-z 构成的。
• 保证所有输入均为非空字符串。

2. 什么是 Trie 树（前缀树）？

在深入解题之前，我们必须先理解这个数据结构。

想象一个场景：你有一个巨大的英语词典，包含数百万个单词。现在，我给你一个前缀，比如 “app”，让你快速找出所有以 “app” 开头的单词（如 “apple", "application", "apprentice”）。如果用普通的数组或哈希表，你需要遍历所有单词，效率极低。

Trie 树就是为了解决这类“前缀检索”问题而生的。

它的核心思想是：用字符串的公共前缀来减少不必要的比较，从而达到快速检索的目的。

一个形象的比喻：
把 Trie 树想象成一棵多叉树，从根节点到某个节点的路径上所经过的字符连接起来，就是该节点对应的字符串。

• 根节点（Root）：不包含字符，是整棵树的起点。
• 每个节点：包含一个字符（实际上，节点本身并不存储字符，字符是通过节点间的链接隐含的），以及若干个子节点指针（比如 26 个，对应 26 个小写字母）。
• 标志位：每个节点还需要一个布尔类型的标志位 isEnd，用来表示从根节点到当前节点的路径是否构成了一个完整的单词（而不仅仅是一个前缀）。

以插入 “apple”, “app” 为例的图示：

        (根节点 Root)
         /
        a (isEnd=false)
         \
          p (isEnd=false)
           \
            p (isEnd=true)  <-- 到这里构成了 "app"
             \
              l (isEnd=false)
               \
                e (isEnd=true) <-- 到这里构成了 "apple"

• 搜索 “app” 时，我们会沿着 a -> p -> p 的路径走，发现第三个节点 p 的 isEnd 为 true，所以返回 true。
• 在只插入了 “apple” 时，搜索 “app” 也会走到第三个节点 p，但此时它的 isEnd 是 false（因为 “app” 还未被作为一个完整单词插入），所以返回 false。
• 而判断前缀 “app” 是否存在时，我们只需要检查路径 a -> p -> p 是否存在，无需关心 isEnd 的值，所以返回 true。

3. 循序渐进的设计与实现

现在，我们一步步来实现这个数据结构。

步骤一：定义 Trie 节点的结构（TrieNode）

这是最基础的一步。每个节点需要两部分：

1. 一个指向子节点的指针数组 children，大小为 26（对应 26 个小写字母）。
2. 一个布尔值 isEnd，标记当前节点是否是某个单词的结尾。

为什么用数组？
因为字母只有 26 种可能，用数组可以通过索引（‘a’ 对应 0，‘b’ 对应 1，...，‘z’ 对应 25）实现 O(1) 时间复杂度的查找。当然，你也可以用哈希表，这样更通用（可以支持更多字符），但数组对于本题来说更简单高效。

class TrieNode:
    def __init__(self):
        # 初始化一个长度为26的列表，初始值都为 None
        self.children = [None] * 26
        # 标记当前节点是否是一个单词的结束
        self.isEnd = False

步骤二：设计 Trie 类的整体框架

Trie 类本身只需要持有一个根节点。

class Trie:
    def __init__(self):
        # 初始化 Trie 时，创建一个空的根节点
        self.root = TrieNode()

步骤三：实现 insert 方法

目标：将一个字符串插入到 Trie 树中。

算法步骤：

1. 从根节点 current 开始。
2. 遍历要插入的单词 word 的每一个字符 ch。
3. 计算字符 ch 对应的索引：index = ord(ch) - ord(‘a’)。
4. 检查 current 节点的 children 数组中，index 位置是否为空（即为 None）。
   • 如果为空，说明这个字符路径还不存在，我们需要创建一个新的 TrieNode 并放在这个位置。
   • 如果不为空，说明路径已存在，直接移动到该子节点。
5. 将 current 指针移动到 index 对应的子节点，继续处理下一个字符。
6. 当遍历完 word 的所有字符后，此时的 current 节点对应的路径就是整个单词。将 current.isEnd 设置为 True，表示这里有一个完整的单词结束。

    def insert(self, word: str) -> None:
        current = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            # 如果当前字符对应的子节点不存在，则创建一个新的节点
            if current.children[index] is None:
                current.children[index] = TrieNode()
            # 将当前节点指针移动到子节点
            current = current.children[index]
        # 标记最后一个节点，表示一个单词的结束
        current.isEnd = True

步骤四：实现 search 方法

目标：检查字符串 word 是否存在于 Trie 中（必须是一个完整的单词，而不仅仅是前缀）。

算法步骤：

1. 从根节点 current 开始。
2. 遍历 word 的每一个字符 ch。
3. 计算索引 index。
4. 检查 current.children[index] 是否存在。
   • 如果为 None，说明路径中断，word 不存在，直接返回 False。
   • 如果不为 None，则将 current 移动到该子节点。
5. 如果成功遍历完所有字符，这只能说明 word 是 Trie 中的一个前缀。我们还需要检查最后一个节点的 isEnd 标志。
   • 如果 current.isEnd 为 True，返回 True（找到了完整单词）。
   • 如果为 False，返回 False（word 只是一个前缀，未被作为独立单词插入）。

    def search(self, word: str) -> bool:
        current = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            if current.children[index] is None:
                # 路径中断，单词不存在
                return False
            current = current.children[index]
        # 检查最终节点是否是单词的结尾
        return current.isEnd

步骤五：实现 startsWith 方法

目标：检查 Trie 中是否有以前缀 prefix 开头的单词。

算法步骤：
这个方法与 search 几乎完全相同，唯一的区别是：它不需要检查最后一个节点的 isEnd 标志。只要能够从前缀的第一个字符走到最后一个字符，路径是通畅的，就说明存在以该前缀开头的单词。

    def startsWith(self, prefix: str) -> bool:
        current = self.root
        for ch in prefix:
            index = ord(ch) - ord('a')
            if current.children[index] is None:
                # 路径中断，前缀不存在
                return False
            current = current.children[index]
        # 不需要检查 isEnd，只要路径存在，前缀就存在
        return True

4. 完整代码

将以上所有部分组合起来，就是完整的实现：

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:
        current = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            if current.children[index] is None:
                current.children[index] = TrieNode()
            current = current.children[index]
        current.isEnd = True

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

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

# 测试代码，对应题目示例
if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))   # True
    print(trie.search("app"))     # False
    print(trie.startsWith("app")) # True
    trie.insert("app")
    print(trie.search("app"))     # True

5. 复杂度分析

• 时间复杂度：
  • insert：O(L)，其中 L 是插入单词的长度。我们只需要遍历单词的每个字符一次。
  • search：O(L)，同理，只需遍历一次。
  • startsWith：O(L)，同理。
• 空间复杂度：最坏情况下，如果所有单词都没有公共前缀，每个字符都需要新开一个节点，空间复杂度为 O(ΣL)，其中 ΣL 是所有插入单词的字符总数。但因为有大量公共前缀的复用，实际空间效率通常比把所有单词单独存储要好。

6. 总结与延伸

核心思想：Trie 树的精髓在于 “空间换时间” 和 “共享前缀”。通过树形结构，将具有相同前缀的单词存储在重叠的路径上，从而在查询时极大地减少了比较次数。

应用场景：

• 搜索引擎的自动补全（Auto-complete）：输入几个字母，立刻提示可能的搜索词。
• 拼写检查（Spell Check）：快速判断一个单词是否在词典中。
• IP 路由选择：最长前缀匹配算法。
• 其他变种：
  • 压缩 Trie（Compressed Trie）：当树中节点只有一个子节点时，可以将路径合并，节省空间。
  • 后缀树（Suffix Tree）：一种更强大的数据结构，用于字符串的复杂模式匹配。

希望这个从概念到实现的逐步讲解能让你彻底理解 Trie 树！这是构建更复杂字符串算法的一块重要基石。