实现Trie（前缀树）

题目描述
Trie（发音类似"try"）是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。请你实现Trie类，包含插入、搜索和前缀搜索功能。

基本概念
Trie是一种多叉树结构，每个节点包含以下部分：

• 子节点指针数组（通常大小为26，对应26个小写字母）
• 布尔字段isEnd，标记该节点是否为某个单词的结束字符

实现步骤

1. Trie节点设计

class TrieNode:
    def __init__(self):
        self.children = [None] * 26  # 26个字母的子节点
        self.is_end = False          # 标记是否为单词结尾

2. Trie类初始化

class Trie:
    def __init__(self):
        self.root = TrieNode()  # 创建根节点（空节点）
    
    def _char_to_index(self, char):
        """将字符转换为索引（0-25）"""
        return ord(char) - ord('a')

3. 插入操作

• 从根节点开始
• 遍历单词的每个字符：
  • 计算字符对应的位置索引
  • 如果当前节点的子节点指针为空，创建新节点
  • 将当前节点移动到子节点
• 在最后一个节点标记is_end为True

def insert(self, word: str) -> None:
    node = self.root
    for char in word:
        index = self._char_to_index(char)
        if not node.children[index]:
            node.children[index] = TrieNode()  # 创建新节点
        node = node.children[index]  # 移动到子节点
    node.is_end = True  # 标记单词结束

4. 搜索完整单词

• 从根节点开始遍历单词
• 如果遇到某个字符对应的子节点不存在，返回False
• 遍历完成后，检查当前节点的is_end标记

def search(self, word: str) -> bool:
    node = self.root
    for char in word:
        index = self._char_to_index(char)
        if not node.children[index]:
            return False  # 字符不存在
        node = node.children[index]
    return node.is_end  # 检查是否是完整单词

5. 前缀搜索

• 与搜索类似，但只需确认前缀存在即可
• 不需要检查is_end标记

def startsWith(self, prefix: str) -> bool:
    node = self.root
    for char in prefix:
        index = self._char_to_index(char)
        if not node.children[index]:
            return False
        node = node.children[index]
    return True  # 前缀存在

完整代码示例

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def _char_to_index(self, char):
        return ord(char) - ord('a')
    
    def insert(self, word):
        node = self.root
        for char in word:
            index = self._char_to_index(char)
            if not node.children[index]:
                node.children[index] = TrieNode()
            node = node.children[index]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            index = self._char_to_index(char)
            if not node.children[index]:
                return False
            node = node.children[index]
        return node.is_end
    
    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            index = self._char_to_index(char)
            if not node.children[index]:
                return False
            node = node.children[index]
        return True

复杂度分析

• 插入/搜索/前缀搜索的时间复杂度：O(L)，其中L是单词长度
• 空间复杂度：最坏情况O(N×M)，N是单词数，M是平均单词长度

实际应用

• 搜索引擎的自动补全
• 拼写检查器
• IP路由的最长前缀匹配
• 输入法的词库存储