数据结构与算法自学笔记（20）- 前缀树的原理和相关题目

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class044和class045的内容，详细介绍了前缀树（Trie树）的原理和代码实现并总结了前缀树(Trie)在实际算法题目中的应用。前缀树是一种专门用于处理字符串前缀查询的高效数据结构，在搜索引擎、自动补全、拼写检查等场景中有广泛应用。

---

044【必备】前缀树原理和代码详解

前置知识

在学习前缀树之前，需要掌握以下基础知识：

• 讲解008-数据结构分类
• 讲解017-二叉树基本概念
• 讲解019-处理输入和输出-推荐静态空间的实现
• 讲解026-哈希表的使用

前缀树基本概念

什么是前缀树

前缀树（Trie Tree），又叫字典树，是一种树形数据结构：

• 每个样本都从头节点开始，根据前缀字符或前缀数字建出来的一棵大树
• 没有路就新建节点；已经有路了，就复用节点
• 每个节点代表一个字符，从根到某个节点的路径构成一个前缀

前缀树的特点

使用场景：需要根据前缀信息来查询的场景

优点：

• 根据前缀信息选择树上的分支，可以节省大量的时间
• 查询效率高，时间复杂度为O(m)，其中m为字符串长度

缺点：

• 比较浪费空间，空间复杂度与总字符数量和字符种类相关
• 需要预先知道字符集的范围

定制信息：

• pass：有多少个单词经过了这个节点
• end：有多少个单词以这个节点结尾
• 节点的子节点可以用数组或哈希表/字典来存储

核心节点结构

每个前缀树节点通常包含以下信息：

class TrieNode:
    def __init__(self):
        self.pass = 0    # 有多少个单词经过了这个节点
        self.end = 0     # 有多少个单词以这个节点结尾
        self.nexts = []  # 指向子节点的链接（数组或字典）

实现方式一：用类描述（不推荐）

测试链接

• 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/

子节点用数组实现

适用于字符集固定且较小的情况（如26个小写英文字母）：

class Trie1:
    """
    提交时把类名、构造方法改为Trie
    Trie树的实现，子节点用固定长度的数组存储。
    适用于字符集固定且较小的情况（如26个小写英文字母）。
    """
    class _TrieNode:
        def __init__(self):
            # pass: 有多少个单词经过了这个节点
            self.pas = 0
            # end: 有多少个单词以这个节点结尾
            self.end = 0
            # nexts: 指向26个可能的子节点的链接,是一个小数组
            self.nexts = [None] * 26

    def __init__(self):
        """
        初始化Trie树，创建一个空的根节点。
        """
        self._root = self._TrieNode()

    def insert(self, word: str):
        """
        向前缀树中插入一个单词。
        """
        node = self._root
        node.pas += 1
        # 从左往右遍历字符
        for char in word:
            # 由字符，对应成走向哪条路 (0-25)
            path = ord(char) - ord('a')  # ord获取char的ASCII码,a的ASCII码是97
            # 检查这个字符的路径是否已经存在节点
            if not node.nexts[path]:
                node.nexts[path] = self._TrieNode()  # 如果path位置为空，则创建一个新节点
            node = node.nexts[path]
            node.pas += 1
        node.end += 1

    def erase(self, word: str):
        """
        如果之前word插入过前缀树，那么此时删掉一次。
        如果之前word没有插入过前缀树，那么什么也不做。
        """
        if self.countWordsEqualTo(word) > 0:  # 先用countWordsEqualTo方法检查word是否存在
            node = self._root
            node.pas -= 1
            for char in word:
                path = ord(char) - ord('a')
                # 如果删除后，路径上的节点的pass值为0，说明没有其他单词经过此路
                # 可以直接将后续节点删除（在Python中由垃圾回收处理）
                node.nexts[path].pas -= 1
                if node.nexts[path].pas == 0:
                    node.nexts[path] = None
                    return
                node = node.nexts[path]
            node.end -= 1

    def countWordsEqualTo(self, word: str) -> int:
        """
        查询前缀树里，word单词出现了几次。
        """
        node = self._root
        for char in word:
            path = ord(char) - ord('a')
            if not node.nexts[path]:
                return 0
            node = node.nexts[path]  # 循环一次，node就走到下一个节点
        return node.end

    def countWordsStartingWith(self, pre: str) -> int:
        """
        查询前缀树里，有多少单词以pre做前缀。
        """
        node = self._root
        for char in pre:
            path = ord(char) - ord('a')
            if not node.nexts[path]:
                return 0
            node = node.nexts[path]
        return node.pas

子节点用哈希表实现

适用于字符集不固定或非常大的情况，更节省空间：

class Trie2:
    """
    Trie树的实现，子节点用字典存储。
    适用于字符集不固定或非常大的情况，更节省空间。
    """
    class _TrieNode:
        def __init__(self):
            self.pas = 0
            self.end = 0
            # nexts: 存储字符到子节点的映射
            self.nexts = {}

    def __init__(self):
        self._root = self._TrieNode()

    def insert(self, word: str):
        node = self._root
        node.pas += 1
        for char in word:
            if char not in node.nexts:
                node.nexts[char] = self._TrieNode()
            node = node.nexts[char]
            node.pas += 1
        node.end += 1

    def erase(self, word: str):
        if self.countWordsEqualTo(word) > 0:
            node = self._root
            node.pas -= 1
            for char in word:
                next_node = node.nexts[char]
                next_node.pas -= 1
                if next_node.pas == 0:
                    # 如果pass为0，直接从字典中移除该路径
                    node.nexts.pop(char)
                    return
                node = next_node
            node.end -= 1

    def countWordsEqualTo(self, word: str) -> int:
        node = self._root
        for char in word:
            if char not in node.nexts:
                return 0
            node = node.nexts[char]
        return node.end

    def countWordsStartingWith(self, pre: str) -> int:
        node = self._root
        for char in pre:
            if char not in node.nexts:
                return 0
            node = node.nexts[char]
        return node.pas

实现方式二：静态数组实现（推荐）

核心思想

抛弃节点对象的概念，将所有节点信息存储在几个大的全局数组中：

• 使用一个整数 cnt 作为节点编号或索引
• tree[i][j]：表示编号为 i 的节点的第 j 条路（对应某个字符）指向的子节点的编号
• end[i]：表示以编号为 i 的节点结尾的单词数量
• pas[i]：表示经过编号为 i 的节点的单词数量

这种方式内存是静态分配的，且数据在内存中连续，通常有更好的缓存性能。

测试链接

• 测试链接 : https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b

完整实现

import sys

# 如果将来增加了数据量，就改大这个值
MAXN = 150001

# 全局变量模拟 Java 的静态变量
tree = [[0] * 26 for _ in range(MAXN)]
end = [0] * MAXN
pas = [0] * MAXN
cnt = 0

def build():
    """
    初始化/重置Trie。根节点编号为1，总节点数从1开始。
    """
    global cnt
    cnt = 1

def insert(word: str):
    """
    向前缀树中插入一个单词。
    """
    global cnt
    cur = 1
    pas[cur] += 1  # pas[cur]：节点 cur 被经过的次数
    for char in word:
        path = ord(char) - ord('a')
        if tree[cur][path] == 0:  # tree[cur][path]:邻接表的数组实现，记录了从节点 cur 出发，沿着字符 path 能到达的下一个节点
            # 如果路径不存在，创建一个新节点
            cnt += 1
            tree[cur][path] = cnt
        cur = tree[cur][path]
        pas[cur] += 1
    end[cur] += 1

def search(word: str) -> int:
    """
    查询一个单词在前缀树中出现的次数。
    """
    cur = 1
    for char in word:
        path = ord(char) - ord('a')
        if tree[cur][path] == 0:
            return 0
        cur = tree[cur][path]
    return end[cur]

def prefix_number(pre: str) -> int:
    """
    查询以 pre 为前缀的单词数量。
    """
    cur = 1
    for char in pre:
        path = ord(char) - ord('a')
        if tree[cur][path] == 0:
            return 0
        cur = tree[cur][path]
    return pas[cur]

def delete(word: str):
    """
    从前缀树中删除一个单词。
    """
    if search(word) > 0:
        cur = 1
        # 根节点的 pass 值减1
        pas[cur] -= 1
        for char in word:
            path = ord(char) - ord('a')
            # 路径上节点的 pass 值减1
            pas[tree[cur][path]] -= 1
            if pas[tree[cur][path]] == 0:
                # 如果 pass 减到0，说明此路径不再被任何单词使用，可以删除
                tree[cur][path] = 0
                return
            cur = tree[cur][path]
        # 最后一个节点的 end 值减1
        end[cur] -= 1

def clear():
    """
    清空Trie树，为下一个测试用例做准备。
    """
    global tree, end, pas
    for i in range(1, cnt + 1):
        for j in range(26):
            tree[i][j] = 0
        end[i] = 0
        pas[i] = 0

def main():
    """
    处理输入输出的主函数。
    """
    lines = sys.stdin.readlines()
    if not lines:
        return
        
    line_iter = iter(lines)
    
    # 持续读取直到没有输入
    while True:
        try:
            # 为每个测试用例重置/构建Trie
            build()
            
            m_line = next(line_iter)  # next获得迭代器里获得下一个对象
            if not m_line: continue
            m = int(m_line.strip())
            
            for _ in range(m):
                splits = next(line_iter).strip().split(" ")
                op = int(splits[0])
                word = splits[1]
                
                if op == 1:
                    insert(word)
                elif op == 2:
                    delete(word)
                elif op == 3:
                    print("YES" if search(word) > 0 else "NO")
                elif op == 4:
                    print(prefix_number(word))
            
            # 清理本次用例的数据（虽然对于某些OJ，不清理也行，因为是新进程）
            clear()

        except StopIteration:
            break

if __name__ == "__main__":
    main()

前缀树的基本操作

1. 插入操作 (Insert)

def insert(word: str):
    """插入一个单词到前缀树中"""
    node = root
    node.pass += 1  # 根节点被经过
    
    for char in word:
        path = ord(char) - ord('a')  # 计算字符对应的路径
        if not node.nexts[path]:
            node.nexts[path] = TrieNode()  # 创建新节点
        node = node.nexts[path]  # 移动到下一个节点
        node.pass += 1  # 更新经过次数
    
    node.end += 1  # 标记单词结尾

时间复杂度：O(m)，其中m是单词长度
空间复杂度：O(m)，最坏情况下需要创建m个新节点

2. 查找操作 (Search)

def search(word: str) -> int:
    """查找单词在前缀树中的出现次数"""
    node = root
    
    for char in word:
        path = ord(char) - ord('a')
        if not node.nexts[path]:
            return 0  # 路径不存在，单词不在树中
        node = node.nexts[path]
    
    return node.end  # 返回以此节点结尾的单词数量

时间复杂度：O(m)
空间复杂度：O(1)

3. 前缀查询 (Prefix Search)

def countWordsStartingWith(prefix: str) -> int:
    """查询以prefix为前缀的单词数量"""
    node = root
    
    for char in prefix:
        path = ord(char) - ord('a')
        if not node.nexts[path]:
            return 0
        node = node.nexts[path]
    
    return node.pass  # 返回经过此节点的单词数量

时间复杂度：O(m)
空间复杂度：O(1)

4. 删除操作 (Delete)

def delete(word: str):
    """从前缀树中删除一个单词"""
    if search(word) == 0:
        return  # 单词不存在，无需删除
    
    node = root
    node.pass -= 1
    
    for char in word:
        path = ord(char) - ord('a')
        next_node = node.nexts[path]
        next_node.pass -= 1
        
        if next_node.pass == 0:
            # 如果经过次数为0，删除整个分支
            node.nexts[path] = None
            return
        
        node = next_node
    
    node.end -= 1  # 减少结尾标记

时间复杂度：O(m)
空间复杂度：O(1)

前缀树的应用场景

1. 自动补全

前缀树非常适合实现自动补全功能：

def autocomplete(prefix: str, max_suggestions: int = 10) -> List[str]:
    """根据前缀返回自动补全建议"""
    node = root
    
    # 找到前缀对应的节点
    for char in prefix:
        path = ord(char) - ord('a')
        if not node.nexts[path]:
            return []  # 前缀不存在
        node = node.nexts[path]
    
    # 从该节点开始收集所有单词
    suggestions = []
    _collect_words(node, prefix, suggestions, max_suggestions)
    return suggestions

def _collect_words(node, current_prefix, suggestions, max_suggestions):
    """递归收集以当前前缀开始的所有单词"""
    if len(suggestions) >= max_suggestions:
        return
    
    if node.end > 0:
        suggestions.append(current_prefix)
    
    for i in range(26):
        if node.nexts[i]:
            next_char = chr(i + ord('a'))
            _collect_words(node.nexts[i], current_prefix + next_char, 
                          suggestions, max_suggestions)

2. 拼写检查

def spell_check(word: str, max_distance: int = 1) -> List[str]:
    """返回与给定单词编辑距离在max_distance内的所有单词"""
    suggestions = []
    _find_similar_words(root, "", word, 0, max_distance, suggestions)
    return suggestions

def _find_similar_words(node, current_word, target, distance, max_distance, suggestions):
    """使用动态规划找到相似单词"""
    if distance > max_distance:
        return
    
    if node.end > 0 and len(current_word) == len(target):
        if distance <= max_distance:
            suggestions.append(current_word)
    
    # 递归遍历所有可能的路径
    for i in range(26):
        if node.nexts[i]:
            next_char = chr(i + ord('a'))
            # 计算新的编辑距离
            new_distance = distance
            if len(current_word) < len(target) and target[len(current_word)] != next_char:
                new_distance += 1
            
            _find_similar_words(node.nexts[i], current_word + next_char, 
                              target, new_distance, max_distance, suggestions)

3. 单词频率统计

def get_word_frequency_stats():
    """获取前缀树中的单词频率统计"""
    stats = {}
    _collect_frequencies(root, "", stats)
    return stats

def _collect_frequencies(node, current_word, stats):
    """递归收集所有单词及其频率"""
    if node.end > 0:
        stats[current_word] = node.end
    
    for i in range(26):
        if node.nexts[i]:
            next_char = chr(i + ord('a'))
            _collect_frequencies(node.nexts[i], current_word + next_char, stats)

复杂度分析总结

操作	时间复杂度	空间复杂度	说明
插入	O(m)	O(1)	m为单词长度，使用预分配的静态数组
查找	O(m)	O(1)	m为单词长度
前缀查询	O(m)	O(1)	m为前缀长度
删除	O(m)	O(1)	m为单词长度
自动补全	O(m + k)	O(h + k)	m=前缀长度，k=返回结果总字符数，h=树最大深度

空间复杂度（整体）：O(ALPHABET_SIZE × N × M)

• ALPHABET_SIZE：字符集大小（如26）
• N：插入的单词数量
• M：平均单词长度

优化技巧和注意事项

1. 内存优化

压缩前缀树（Compressed Trie）：

• 将只有一个子节点的路径压缩成一条边
• 节省空间，但增加了实现复杂度

数组 vs 哈希表选择：

• 字符集固定且较小：使用数组
• 字符集大或不确定：使用哈希表

2. 性能优化

静态数组实现：

# 推荐使用静态数组，避免频繁的内存分配
MAXN = 150001
tree = [[0] * 26 for _ in range(MAXN)]

批量操作：

def batch_insert(words: List[str]):
    """批量插入，减少函数调用开销"""
    for word in words:
        insert(word)

3. 扩展功能

支持通配符查询：

def wildcard_search(pattern: str) -> List[str]:
    """支持'.'作为通配符的查询"""
    results = []
    _wildcard_dfs(root, pattern, 0, "", results)
    return results

def _wildcard_dfs(node, pattern, index, current_word, results):
    if index == len(pattern):
        if node.end > 0:
            results.append(current_word)
        return
    
    char = pattern[index]
    if char == '.':
        # 通配符，尝试所有可能的字符
        for i in range(26):
            if node.nexts[i]:
                next_char = chr(i + ord('a'))
                _wildcard_dfs(node.nexts[i], pattern, index + 1, 
                            current_word + next_char, results)
    else:
        # 普通字符
        path = ord(char) - ord('a')
        if node.nexts[path]:
            _wildcard_dfs(node.nexts[path], pattern, index + 1, 
                        current_word + char, results)

实战应用示例

LeetCode相关题目

1. 208. 实现 Trie (前缀树)：基础的前缀树实现
2. 211. 添加与搜索单词：支持通配符的前缀树
3. 212. 单词搜索 II：在二维网格中搜索单词
4. 421. 数组中两个数的最大异或值：使用前缀树优化位运算
5. 648. 单词替换：使用前缀树实现单词替换

工程实践建议

1. 选择合适的实现方式：

   • 简单应用：使用类实现
   • 高性能要求：使用静态数组
   • 内存敏感：使用哈希表

2. 内存管理：

   • 及时清理不需要的节点
   • 考虑使用对象池减少GC压力

3. 并发安全：

   • 读写分离
   • 使用读写锁
   • 考虑无锁数据结构

总结

前缀树是一种强大的字符串处理数据结构，特别适合：

• 前缀查询：快速找到所有具有特定前缀的字符串
• 自动补全：实现搜索建议功能
• 拼写检查：找到相似的单词
• 字符串匹配：高效的模式匹配

通过合理选择实现方式和优化策略，前缀树可以在保持高效性能的同时，提供丰富的字符串操作功能。在实际应用中，需要根据具体的使用场景选择最适合的实现方案。

---

045【必备】前缀树的相关题目

前置知识

在学习前缀树相关题目之前，需要掌握以下基础知识：

• 讲解044：前缀树原理和代码详解-静态空间的方式实现
• 基本的字符串操作和递归思想
• 深度优先搜索(DFS)的基本概念

前缀树基础回顾

核心数据结构

# 前缀树的全局变量设计
MAXN = 2000001  # 根据题目数据规模调整

# tree[i][j] 表示编号为i的节点，走向字符j的下一个节点编号
tree = [[0] * 字符集大小 for _ in range(MAXN)]
# pas[i] 表示编号为i的节点被多少个字符串经过
pas = [0] * MAXN
# end[i] 表示编号为i的节点是否为某个字符串的结尾
end = [0] * MAXN  # 或存储具体的字符串
cnt = 0  # 节点计数器

基本操作模板

def build():
    """初始化Trie，根节点编号为1"""
    global cnt
    cnt = 1

def insert(word: str):
    """将字符串插入Trie"""
    global cnt
    cur = 1
    pas[cur] += 1
    for char in word:
        path = get_path(char)  # 将字符映射到路径索引
        if tree[cur][path] == 0:
            cnt += 1
            tree[cur][path] = cnt
        cur = tree[cur][path]
        pas[cur] += 1
    end[cur] = word  # 或设置为True

def search(word: str) -> bool:
    """搜索字符串是否存在"""
    cur = 1
    for char in word:
        path = get_path(char)
        if tree[cur][path] == 0:
            return False
        cur = tree[cur][path]
    return end[cur] is not None

def count_prefix(prefix: str) -> int:
    """计算以prefix为前缀的字符串数量"""
    cur = 1
    for char in prefix:
        path = get_path(char)
        if tree[cur][path] == 0:
            return 0
        cur = tree[cur][path]
    return pas[cur]

---

题目一：接头密匙（差值序列匹配）

问题描述

牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份。密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：

• 密匙 b 的长度不超过密匙 a 的长度
• 对于任意 0 <= i < length(b)，有 b[i+1] - b[i] == a[i+1] - a[i]

现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组，请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙。

测试链接：https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932

核心思想

问题的关键在于比较”差值序列”，而不是原始数字序列：

1. 差值序列转换：将每个键 a (如 [3, 6, 50]) 转换为其差值字符串 (如 “3#44#”)
2. 前缀树构建：将所有 a 的差值字符串插入到一个前缀树 (Trie) 中。每个节点记录有多少个字符串经过它 (pass计数)
3. 前缀匹配查询：对于每个键 b，将其转换为差值字符串，在Trie中查询以此为前缀的字符串数量
4. 一致性判定：这个数量就是与 b 一致的 a 的数量。因为如果 a 的差值序列以 b 的差值序列为前缀，就满足题目中的“一致”条件

算法实现

# 如果将来增加了数据量，就改大这个值
MAXN = 2000001

# 全局变量模拟 Java 的静态变量
tree = [[0] * 12 for _ in range(MAXN)]
pas = [0] * MAXN
cnt = 0

def build():
    """初始化Trie，根节点编号为1"""
    global cnt
    cnt = 1

# '0'~'9' -> 0~9, '#' -> 10, '-' -> 11 
def get_path(char: str) -> int:
    """将字符映射到Trie的路径索引"""
    if char == '#':
        return 10
    elif char == '-':  # - 是负差值
        return 11
    else:
        return int(char)

def insert(word: str):
    """将差值字符串插入Trie"""
    global cnt
    cur = 1
    pas[cur] += 1
    for char in word:
        path = get_path(char)
        if tree[cur][path] == 0:
            cnt += 1
            tree[cur][path] = cnt
        cur = tree[cur][path]
        pas[cur] += 1

def count(pre: str) -> int:
    """计算以 pre 为前缀的字符串数量"""
    cur = 1
    for char in pre:
        path = get_path(char)
        if tree[cur][path] == 0:
            return 0
        cur = tree[cur][path]
    return pas[cur]

def count_consistent_keys(b, a):
    """主函数，处理接头密匙逻辑"""
    build()
    
    # 将所有 a 的差值序列插入Trie
    for nums in a:
        diff_str_parts = []
        for i in range(1, len(nums)):
            diff_str_parts.append(str(nums[i] - nums[i-1]))
            diff_str_parts.append("#")
        insert("".join(diff_str_parts))
    
    ans = [0] * len(b)
    # 查询每个 b 的差值序列在前缀树中的计数
    for i in range(len(b)):
        nums = b[i]
        if len(nums) <= 1:
            # 如果 b 只有一个或零个元素，差值序列为空
            # 空前缀匹配所有插入的 a，所以结果是 a 的总数
            ans[i] = len(a)
        else:
            diff_str_parts = []
            for j in range(1, len(nums)):
                diff_str_parts.append(str(nums[j] - nums[j-1]))
                diff_str_parts.append("#")
            ans[i] = count("".join(diff_str_parts))
    
    return ans

算法分析

• 时间复杂度：O(a数组的数字个数 * 10) + O(b数组的数字个数 * 10)
• 空间复杂度：O(a数组的数字个数 * 10)，这是树上的节点数量
• 核心技巧：差值序列 + 前缀匹配

---

题目二：数组中两个数的最大异或值

问题描述

给你一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n。

测试链接：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

算法实现

方法一：前缀树解法

核心思想

使用前缀树存储所有数字的二进制表示，然后贪心地寻找最大异或值：

1. 二进制Trie构建：将所有数字的二进制表示（从高位到低位）插入到一个Trie中
2. 贪心搜索：遍历每个数字 num，然后在Trie中为它寻找一个最佳的配对 x，以最大化 num XOR x
3. 位级贪心：寻找最佳配对的过程是贪心的：从最高位开始，对于 num 的每一位，我们都期望在Trie中找到与之相反的位。如果Trie中存在相反位的路径，我们就走这条路，这会使结果的当前位为1。如果不存在，我们只能走相同位的路径，结果的当前位为0
4. 最优解更新：遍历所有数字，找到全局最大异或值

具体实现

MAXN = 3000001
tree = [[0] * 2 for _ in range(MAXN)]
cnt = 0
high = 0

def build(nums):
    """构建Trie树，插入所有数字的二进制表示"""
    global cnt, high
    cnt = 1
    # 找到数组中的最大值，以确定需要处理的二进制位数
    maximum = max(nums) if nums else 0
    # high: 最高位的索引。例如，max=13(1101), bit_length=4, high=3
    high = maximum.bit_length() - 1 if maximum > 0 else -1 #bit_length返回的是二进制所需的位数，maximum>0表示没有有效位数
    for num in nums:
        insert(num)

def insert(num):
    """将一个数字的二进制位插入Trie"""
    global cnt
    cur = 1
    # 从最高有效位开始
    for i in range(high, -1, -1):
        path = (num >> i) & 1 #将 num 的二进制表示向右移动 i 位，结果只保留最低位（第0位）
        if tree[cur][path] == 0:
            cnt += 1
            tree[cur][path] = cnt
        cur = tree[cur][path]

def max_xor(num): #就前缀树的这个
    """对于给定的num，在Trie中寻找能使其异或结果最大的数"""
    ans = 0
    cur = 1
    for i in range(high, -1, -1):
        # status: num 在第 i 位的状态 (0 or 1)
        status = (num >> i) & 1 
        # want: 希望遇到的对方路径，即与 status相反的位，这样异或结果在该位上是1
        want = 1 - status
        # 检查Trie中是否存在期望的路径
        if tree[cur][want] == 0:
            # 如果期望的路径不存在，只能走另一条路
            want = 1 - want
        
        # (status ^ want) 是当前位实际的异或结果
        # 将其左移 i 位，加到 ans 中
        ans |= (status ^ want) << i #计算当前位的异或结果，将结果左移到正确的位置，累加到最终答案中
        cur = tree[cur][want] #在Trie树中移动到下一个节点
    return ans

def clear():
    """清空Trie"""
    for i in range(1, cnt + 1):
        tree[i][0] = tree[i][1] = 0

def findMaximumXOR1(nums):
    """
    Trie解法主函数
    """
    if not nums or len(nums) < 2:
        return 0
    build(nums)
    ans = 0
    for num in nums:
        ans = max(ans, max_xor(num))
    clear()
    return ans

方法二：哈希表解法

核心思想

使用前缀树存储所有数字的二进制表示，然后贪心地寻找最大异或值：

1. 假设我们已经确定了最大值的前k位（从高到低），结果是 ans。
2. 现在我们来确定第 i 位。我们贪心地希望第 i 位是 1。
   令我们的目标 better = ans | (1 << i)。
3. 问题转化为：是否存在两个数 p 和 q，使得 (p XOR q) 的前缀等于 better？
   这等价于 p 的前缀等于 better 的前缀 XOR q 的前缀。
4. 我们将所有数字的前缀（保留高位，低位置0）放入一个哈希集合 set 中。
5. 然后遍历这个集合，对于每个前缀 p_prefix，检查 better ^ p_prefix 是否也在集合中。
6. 如果在，说明 better 这个目标是可以达成的，我们就更新 ans = better。
   否则，第 i 位只能是 0，ans 保持不变。
7. 重复此过程直到最低位。

具体实现

def findMaximumXOR2(nums):
    """
    哈希表解法主函数
    核心思想：
    从最高位向最低位，一位一位地确定最大异或值的可能值。
    """
    if not nums or len(nums) < 2:
        return 0
    maximum = max(nums)
    high_bit = maximum.bit_length() - 1 if maximum > 0 else -1
    
    ans = 0
    seen_prefixes = set()
    for i in range(high_bit, -1, -1):
        # 贪心目标：尝试让第 i 位为 1
        better = ans | (1 << i)
        seen_prefixes.clear() # 先clear掉hashset里的所有元素
        
        # 将所有数字的 i-位前缀放入集合
        for num in nums:
            seen_prefixes.add(num >> i)
            
        # 检查 better 这个前缀是否可以由集合中的某两个数异或得到
        # a ^ b = c  <=>  a ^ c = b
        found = False
        for p in seen_prefixes: #遍历hashset里的所有元素
            if (better >> i) ^ p in seen_prefixes:
                ans = better
                found = True
                break
        # if any(((better >> i) ^ p) in seen_prefixes for p in seen_prefixes):
        #     ans = better

    return ans

算法分析

• 时间复杂度：O(n * logV)，V是数值范围
• 空间复杂度：O(n * logV)
• 核心技巧：二进制前缀树 + 贪心搜索

---

题目三：在二维字符数组中搜索可能的单词

问题描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中”相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

测试链接：https://leetcode.cn/problems/word-search-ii/

核心思想

结合前缀树和深度优先搜索，实现高效的多单词同时搜索：

1. 前缀树构建：将所有 words 构建成一棵前缀树。这使得我们可以同时搜索所有的单词。
2. DFS：从 board 的每一个单元格出发，进行深度优先搜索（DFS）。
3. Trie同步：DFS 的每一步不仅在 board 上移动，也同步在前缀树上移动。
4. 如果在 board 上的路径能在前缀树中走通，说明这个路径是一个或多个单词的前缀。
5. 如果走到了一个前缀树的 end 节点，说明找到了一个单词，将其加入结果集。
6. 剪枝优化：
   a. 在DFS中，如果前缀树的某个路径后续没有单词了（pass计数为0），则停止该方向的搜索。
   b. 找到一个单词后，将其从前缀树中“逻辑删除”（如将end设为None），并更新pass计数，避免重复查找和无效搜索。
7. 回溯处理：使用哨兵值标记已访问格子，回溯时恢复现场

算法实现

from typing import List

# 全局变量模拟静态数组
MAXN = 30001  # words.length * words[i].length
tree = [[0] * 26 for _ in range(MAXN)]
pas = [0] * MAXN
end = [None] * MAXN
cnt = 0

def build(words: List[str]):
    """将所有待查单词构建成一棵Trie树"""
    global cnt
    cnt = 1
    for word in words:
        cur = 1
        pas[cur] += 1
        for char in word:
            path = ord(char) - ord('a')
            if tree[cur][path] == 0:
                cnt += 1
                tree[cur][path] = cnt # 把当前节点 cur 在这条路径 path 上的“指针”设为新节点编号
            cur = tree[cur][path] # 在Trie树中移动到下一个节点
            pas[cur] += 1
        end[cur] = word

def clear():
    """清理Trie树"""
    for i in range(1, cnt + 1):
        for j in range(26):
            tree[i][j] = 0
        pas[i] = 0
        end[i] = None

def dfs(board: List[List[str]], i: int, j: int, t: int, ans: List[str]) -> int:
    """
    深度优先搜索函数
    
    board: 二维网格
    i, j: 当前格子位置
    t: 当前在前缀树中的节点编号
    ans: 结果列表，里面是收集到的字符串
    返回值: 从 (i,j) 出发，新收集到了几个字符串
    """
    # 大剪枝：i，j越界 或 走了回头路(board[i][j] == 0，即ascii码=0)，直接返回
    if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or board[i][j] == 0:
        return 0
    
    tmp = board[i][j]
    road = ord(tmp) - ord('a') #路的编号而不是节点的编号
    # t: 当前节点, tree[t][road]: 下一节点
    t_next = tree[t][road]

    # 剪枝：如果后续路径上没有任何单词（t_next == 0）或者结果已经收集全了(pas[t_next] == 0)，则无需继续搜索。不过其实这两个条件是等价的
    if t_next == 0: # or pas[t_next] == 0:
        return 0
    
    # fix: 从当前 (i, j) 位置出发，总共收集到了几个新字符串
    fix = 0
    # 如果当前Trie节点是一个单词的结尾
    if end[t_next] is not None:
        fix += 1
        ans.append(end[t_next]) # 前缀树的尽头
        # 防止重复添加
        end[t_next] = None
    
    # 标记当前位置已访问
    board[i][j] = 0
    # 向上、下、左、右四个方向递归搜索
    fix += dfs(board, i - 1, j, t_next, ans)
    fix += dfs(board, i + 1, j, t_next, ans)
    fix += dfs(board, i, j - 1, t_next, ans)
    fix += dfs(board, i, j + 1, t_next, ans)
    
    # 剪枝优化：回溯时，更新Trie树的pass计数。
    # fix是本次DFS调用中找到的单词总数。
    # 将这些单词从后续的搜索路径中“移除”，避免不必要的搜索。
    pas[t_next] -= fix # 把本次从 t_next 开始的 DFS 一共找到的单词数 fix，从该 Trie 节点的经过计数 pas[t_next] 中减掉
    # 回溯：恢复现场。过程：进入格子前保存字符到 tmp → 标记已访问为 0（哨兵，避免重复走）→ 递归结束后把 board[i][j] 设回 tmp，这样其他路径还能正常使用该格子。
    board[i][j] = tmp
    return fix

def findWords(board: List[List[str]], words: List[str]) -> List[str]:
    """
    主函数
    """
    build(words)
    ans = []
    for i in range(len(board)):
        for j in range(len(board[0])):
            dfs(board, i, j, 1, ans) # 根节点编号为1
    clear()
    return ans

算法分析

• 时间复杂度：O(m * n * 4^L)，L是最长单词长度
• 空间复杂度：O(总字符数)
• 核心技巧：前缀树 + DFS + 动态剪枝

---

前缀树应用总结

1. 适用场景分析

场景类型	典型特征	前缀树优势
前缀匹配	查询以某字符串为前缀的内容	O(L)查询，支持前缀计数
多模式匹配	同时搜索多个字符串	共享前缀，减少重复搜索
字符串编码	处理字符到数字的映射	灵活的路径编码方案
动态剪枝	搜索过程中动态优化	pass计数支持智能剪枝

2. 设计要点

字符映射策略

# 根据字符集选择合适的映射方案
def get_path(char):
    if char.isdigit():
        return int(char)  # 数字字符
    elif char.isalpha():
        return ord(char) - ord('a')  # 字母字符
    else:
        return 特殊字符映射  # 如'#'->10, '-'->11

节点信息设计

# 根据需求选择节点存储的信息
pas[i] = 经过次数      # 支持前缀计数
end[i] = 是否结尾      # 支持单词判定
end[i] = 完整单词      # 支持单词返回

剪枝优化策略

# 多种剪枝技巧组合使用
if tree[cur][path] == 0:    # 路径不存在剪枝
    return
if pas[cur] == 0:           # 无有效单词剪枝
    return
pas[cur] -= found_count     # 动态更新剪枝

3. 性能优化技巧

空间优化

• 合理评估MAXN大小，避免内存浪费
• 及时清理无用节点，重复利用空间
• 考虑使用哈希表替代数组（适用于稀疏情况）

时间优化

• 预计算字符映射函数，避免重复计算
• 使用位运算优化二进制操作
• 合理设计剪枝条件，减少无效搜索

代码优化

# 通用的前缀树工具类设计
class TrieTree:
    def __init__(self, charset_size=26):
        self.MAXN = 100001
        self.tree = [[0] * charset_size for _ in range(self.MAXN)]
        self.pas = [0] * self.MAXN
        self.end = [False] * self.MAXN
        self.cnt = 1
    
    def clear(self):
        for i in range(1, self.cnt + 1):
            for j in range(len(self.tree[i])):
                self.tree[i][j] = 0
            self.pas[i] = 0
            self.end[i] = False
        self.cnt = 1

4. 常见错误避免

边界处理

• 空字符串的处理
• 单字符串的特殊情况
• 数组越界检查

状态管理

• 全局变量的正确初始化和清理
• 递归过程中状态的正确传递
• 回溯时现场的完整恢复

逻辑正确性

• 前缀匹配 vs 完全匹配的区别
• 路径索引映射的一致性
• 剪枝条件的准确性

学习建议

1. 掌握基础操作

• 熟练掌握前缀树的构建、插入、查询操作
• 理解pass计数和end标记的作用
• 练习不同字符集的映射方案

2. 理解应用场景

• 识别哪些问题适合用前缀树解决
• 学会将复杂问题转化为前缀匹配问题
• 掌握前缀树与其他算法的结合使用

3. 优化思维培养

• 学会分析时间空间复杂度
• 掌握各种剪枝优化技巧
• 培养动态调整搜索策略的能力

4. 实战经验积累

• 多做不同类型的前缀树题目
• 总结常见的代码模板和套路
• 练习在限时条件下的快速实现

通过系统学习前缀树的这些经典应用，可以很好地理解前缀树在实际算法问题中的强大作用，为解决更复杂的字符串和搜索问题打下坚实基础。