字典树（Trie）

Trie 概览

Trie（前缀树）将字符串逐字符存入树中，共享公共前缀。单次插入/查找时间 O(L)，L 为字符串长度，与字典大小无关。

操作复杂度

Trie vs HashMap

基础 Trie

节点含两个字段：children[26]（或 unordered_map）和 isEnd 标记。insert() 沿路创建缺失节点；search() 沿路前进，结尾检查 isEnd；startsWith() 同 search() 但不检查 isEnd。

struct TrieNode {
    TrieNode* children[26] = {};
    bool isEnd = false;
};

class Trie {
    TrieNode* root = new TrieNode();
public:
    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx])
                cur->children[idx] = new TrieNode();
            cur = cur->children[idx];
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return cur->isEnd;
    }

    bool startsWith(const string& prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return true;
    }
};

典型题目

• 208. 实现 Trie（前缀树）
• 1268. 搜索推荐系统（前缀匹配 + 排序）
• 820. 单词的压缩编码（后缀字典树）

children 的选择：仅小写字母用 children[26] 固定数组，空间浪费但速度快；字符集大时改用 unordered_map'<'char, TrieNode*'>'。

Trie + DFS：单词搜索

212. 单词搜索 II：将所有单词插入 Trie，然后 DFS 遍历网格。在 Trie 中前进：若当前节点的 isEnd 为 true 则记录单词；若子节点不存在则剪枝。

优势

• 同时搜索多个单词，比对每个单词分别 DFS 快 O(单词数) 倍
• 剪枝：Trie 中无匹配前缀时立即停止，避免无效 DFS 分支
• 找到单词后可从 Trie 删除（isEnd = false），避免重复添加

复杂度：DFS O(M × N × 4^L) 最坏，但 Trie 剪枝可大幅降低实际运行时间，L 为最长单词长度。

XOR Trie：最大异或

XOR Trie 将整数按位（从高位到低位）插入二叉 Trie。查询最大 XOR 时贪心选取与当前位相反的分支（若存在），使 XOR 尽可能大。单次操作 O(32) 或 O(31)。

// XOR Trie — find max XOR of any two numbers in array
struct XorTrie {
    int ch[2];
    XorTrie() { ch[0] = ch[1] = 0; }
};

vector<XorTrie> trie(1);

void insert(int x) {
    int cur = 0;
    for (int bit = 30; bit >= 0; bit--) {
        int b = (x >> bit) & 1;
        if (!trie[cur].ch[b]) {
            trie.emplace_back();
            trie[cur].ch[b] = trie.size() - 1;
        }
        cur = trie[cur].ch[b];
    }
}

int query(int x) {
    int cur = 0, res = 0;
    for (int bit = 30; bit >= 0; bit--) {
        int b = (x >> bit) & 1;
        int want = 1 - b; // try the opposite bit
        if (trie[cur].ch[want]) { res |= (1 << bit); cur = trie[cur].ch[want]; }
        else cur = trie[cur].ch[b];
    }
    return res;
}

int findMaximumXOR(vector<int>& nums) {
    trie.assign(1, XorTrie());
    int ans = 0;
    for (int x : nums) {
        insert(x);
        ans = max(ans, query(x));
    }
    return ans;
}

典型题目

• 421. 数组中两个数的最大异或值
• 1803. 统计异或值在范围内的数对有多少

位顺序：从最高有效位（MSB，通常是第 30 或 31 位）向低位插入，保证贪心选择时高位优先（贡献值更大）。