实现 Trie (前缀树)

本文详细解析 LeetCode 208 题“实现 Trie (前缀树)”，提供 Python 实现，涵盖插入、搜索和前缀匹配操作，并附有完整代码。

Leetcode Python 前缀树哈希表

阅读要点

Trie 节点结构：每个节点包含一个长度为 26 的数组和结束标志
insert 操作：遍历字符，创建缺失节点，最后标记结束
search 操作：利用 searchPrefix 查找前缀，并检查结束标志
startsWith 操作：仅检查前缀是否存在

题目

208. 实现 Trie (前缀树) - 力扣（LeetCode）

解法

Trie（前缀树）是一种用于高效存储和检索字符串集合的树形数据结构。每个节点代表一个字符，最多有 26 个子节点（针对小写字母）。通过共享前缀，Trie 可以显著减少存储空间，并支持快速的插入、搜索和前缀匹配操作。

基本思想

根节点不包含字符，除根节点外每个节点包含一个字符。
从根节点到某一节点的路径上经过的字符连接起来，即为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。

操作说明

insert(word)：从根节点开始，遍历 word 的每个字符，若当前节点的子节点不存在，则创建新节点，然后移动到子节点。遍历结束后，将当前节点的 end 标记设为 True，表示该节点对应一个完整的单词。
search(word)：调用 searchPrefix 查找前缀，若返回的节点存在且 end 为 True，则说明 word 存在。
startsWith(prefix)：调用 searchPrefix 查找前缀，若返回的节点存在，则说明存在以 prefix 为前缀的单词。

答案

class Trie:
 
    def __init__(self):
        self.child = [None] * 26
        self.end = False
 
    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            ch_id = ord(ch) - ord('a')
            if not node.child[ch_id]:
                node.child[ch_id] = Trie()
            node = node.child[ch_id]
        node.end = True
 
    def searchPrefix(self, prefix: str):
        node = self
        for ch in prefix:
            ch_id = ord(ch) - ord('a')
            if node.child[ch_id]:
                node = node.child[ch_id]
            else:
                return None
        return node
 
    def search(self, word: str) -> bool:
        res = self.searchPrefix(word)
        if not res or not res.end:
            return False
        return True
 
    def startsWith(self, prefix: str) -> bool:
        res = self.searchPrefix(prefix)
        if not res:
            return False
        return True
 
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

复杂度分析

时间复杂度：插入、搜索和前缀匹配均为 O(L)，其中 L 为字符串长度。
空间复杂度：最坏情况下，所有插入的字符串没有公共前缀，则节点数为所有字符串长度之和，空间复杂度为 O(N*L)，其中 N 为字符串数量。