字典树(Trie)

字典树，也称前缀树(Prefix Tree)或Trie树，是一种高效的字符串检索数据结构，特别适用于处理字符串集合的查找、插入和前缀匹配操作。

基本概念

【定义】字典树是一种多叉树结构，每个节点存储一个字符，从根节点到某一节点的路径上的字符连接起来表示一个字符串。树的每个节点可能有多个子节点，每个子节点代表不同的字符。

【特点】

• 根节点不包含字符
• 从根节点到某个节点的路径上的字符连接起来表示一个字符串
• 每个节点的子节点代表不同的字符（通常用数组或哈希表存储）
• 用额外的标志表示一个完整的单词

基本结构

节点定义

// Trie节点结构
struct TrieNode {
    bool isEndOfWord;  // 标记该节点是否是一个单词的结尾
    TrieNode* children[26];  // 假设只处理小写字母a-z

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

Trie树类

// Trie树类
class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 析构函数删除所有节点
    ~Trie() {
        clear(root);
    }

    // 递归删除节点
    void clear(TrieNode* node) {
        if (node) {
            for (int i = 0; i < 26; i++) {
                if (node->children[i]) {
                    clear(node->children[i]);
                }
            }
            delete node;
        }
    }

    // 插入一个单词
    void insert(string word) {
        TrieNode* curr = root;
        for (char c : word) {
            int index = c - 'a';
            if (!curr->children[index]) {
                curr->children[index] = new TrieNode();
            }
            curr = curr->children[index];
        }
        curr->isEndOfWord = true;  // 标记单词结束
    }

    // 搜索一个单词
    bool search(string word) {
        TrieNode* node = searchPrefix(word);
        return node != nullptr && node->isEndOfWord;
    }

    // 判断是否有以给定前缀开头的单词
    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }

private:
    // 查找前缀，返回最后一个匹配节点
    TrieNode* searchPrefix(string prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (!curr->children[index]) {
                return nullptr;  // 前缀不存在
            }
            curr = curr->children[index];
        }
        return curr;
    }
};

操作复杂度

• 插入操作：O(m)，其中m是单词的长度
• 查找操作：O(m)，其中m是查找词的长度
• 前缀查找：O(m)，其中m是前缀的长度
• 空间复杂度：O(n*m)，其中n是单词数量，m是平均单词长度

优化与变种

数组优化为Map

当字符集较大或稀疏时，可以使用map代替数组来节省空间：

// 使用map优化的Trie节点
struct TrieNode {
    bool isEndOfWord;
    unordered_map<char, TrieNode*> children;

    TrieNode() : isEndOfWord(false) {}
};

计数Trie

在每个节点中添加计数，用于统计单词出现次数：

// 计数Trie节点
struct TrieNode {
    int count;  // 以此节点结尾的单词数
    int prefixCount;  // 以此节点对应字符串为前缀的单词数
    TrieNode* children[26];

    TrieNode() : count(0), prefixCount(0) {
        memset(children, 0, sizeof(children));
    }
};

压缩Trie (Patricia Trie)

压缩Trie合并只有一个子节点的节点，减少存储空间：

// 压缩Trie节点
struct PatriciaNode {
    string segment;  // 存储一个字符串段，而不是单个字符
    bool isEndOfWord;
    unordered_map<char, PatriciaNode*> children;

    PatriciaNode(string s = "") : segment(s), isEndOfWord(false) {}
};

01-Trie

用于处理二进制串或整数，每个节点只有0和1两个子节点：

// 01-Trie节点
struct BinaryTrieNode {
    BinaryTrieNode* children[2];  // 只有0和1两个子节点
    bool isEndOfNumber;

    BinaryTrieNode() : isEndOfNumber(false) {
        children[0] = children[1] = nullptr;
    }
};

// 插入整数
void insertNumber(BinaryTrieNode* root, int num, int bitLength = 31) {
    BinaryTrieNode* curr = root;
    for (int i = bitLength - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!curr->children[bit]) {
            curr->children[bit] = new BinaryTrieNode();
        }
        curr = curr->children[bit];
    }
    curr->isEndOfNumber = true;
}

应用场景

1. 字符串检索与前缀匹配

// 获取所有以给定前缀开头的单词
vector<string> getWordsWithPrefix(TrieNode* root, string prefix) {
    vector<string> result;
    TrieNode* node = findPrefix(root, prefix);
    if (!node) return result;

    collectWords(node, prefix, result);
    return result;
}

void collectWords(TrieNode* node, string currentPrefix, vector<string>& result) {
    if (node->isEndOfWord) {
        result.push_back(currentPrefix);
    }

    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            collectWords(node->children[i], currentPrefix + char('a' + i), result);
        }
    }
}

2. 最长公共前缀

// 查找字符串数组的最长公共前缀
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";

    Trie trie;
    for (string& s : strs) {
        trie.insert(s);
    }

    string prefix = strs[0];
    TrieNode* curr = trie.getRoot();
    int len = 0;

    for (char c : prefix) {
        int index = c - 'a';
        // 如果当前节点有超过一个子节点，或者是某个单词的结尾，则停止
        int childCount = 0;
        for (int i = 0; i < 26; i++) {
            if (curr->children[i]) childCount++;
        }

        if (childCount > 1 || curr->isEndOfWord) break;

        curr = curr->children[index];
        len++;
    }

    return prefix.substr(0, len);
}

3. 单词替换

// 使用字典中最短的词替换句子中的单词
string replaceWords(vector<string>& dictionary, string sentence) {
    Trie trie;
    for (string& root : dictionary) {
        trie.insert(root);
    }

    stringstream ss(sentence);
    string word, result;

    while (ss >> word) {
        string replacement = findShortestPrefix(trie.getRoot(), word);
        if (!result.empty()) result += " ";
        result += replacement.empty() ? word : replacement;
    }

    return result;
}

string findShortestPrefix(TrieNode* root, string word) {
    string prefix;
    TrieNode* curr = root;

    for (char c : word) {
        int index = c - 'a';
        if (!curr->children[index]) break;

        prefix += c;
        curr = curr->children[index];

        if (curr->isEndOfWord) return prefix;  // 找到最短前缀
    }

    return "";  // 没有匹配的前缀
}

4. 字典序第K小数

// 查找Trie中字典序第k小的数
string findKthString(TrieNode* root, int k) {
    // 计算Trie中每个节点下的单词数
    countWords(root);

    return findKth(root, k);
}

int countWords(TrieNode* node) {
    if (!node) return 0;

    int count = node->isEndOfWord ? 1 : 0;
    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            count += countWords(node->children[i]);
            node->childrenCount[i] = count;
        }
    }

    return count;
}

string findKth(TrieNode* node, int& k) {
    if (!node) return "";

    if (node->isEndOfWord) {
        k--;
        if (k == 0) return "";
    }

    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            if (node->childrenCount[i] >= k) {
                return char('a' + i) + findKth(node->children[i], k);
            } else {
                k -= node->childrenCount[i];
            }
        }
    }

    return "";
}

5. 最大异或对

在 01-Trie 中查找与给定数异或值最大的数：

// 查找与num异或值最大的数
int findMaxXOR(BinaryTrieNode* root, int num, int bitLength = 31) {
    BinaryTrieNode* curr = root;
    int result = 0;

    for (int i = bitLength - 1; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int oppositeBit = 1 - bit;  // 相反的位

        // 尝试走与当前位相反的路径，这样异或结果为1
        if (curr->children[oppositeBit]) {
            result |= (1 << i);  // 设置结果的当前位为1
            curr = curr->children[oppositeBit];
        } else {
            curr = curr->children[bit];
        }
    }

    return result;
}

实现技巧与优化

1. 边界处理

• 检查空字符串和空Trie
• 处理节点不存在的情况
• 处理字符集范围外的字符

2. 减少内存使用

• 对于大量短字符串，使用位压缩表示
• 短前缀的情况下，用数组代替map提高效率
• 适当删除不再需要的Trie节点

3. 批量操作优化

• 构建Trie时可以一次性排序并插入
• 利用排序减少重复前缀的处理

练习题目推荐

1. LC 208: Implement Trie (基本Trie树实现)
2. LC 211: Design Add and Search Words Data Structure (支持通配符的Trie)
3. LC 212: Word Search II (Trie + DFS)
4. LC 421: Maximum XOR of Two Numbers in an Array (01-Trie应用)
5. LC 648: Replace Words (前缀替换)
6. LC 677: Map Sum Pairs (Trie计数应用)
7. POJ 2001: Shortest Prefixes (最短唯一前缀)
8. POJ 2513: Colored Sticks (Trie + 并查集)

总结

字典树(Trie)是一种高效的字符串检索数据结构，在处理大量字符串的前缀匹配、查询和存储方面具有显著优势。虽然相比哈希表，它在单个操作上可能并不总是最快的，但在处理字符串集合的整体操作时，特别是涉及前缀时，Trie往往能提供最优的性能。

01-Trie在处理二进制或整数问题时特别有用，如最大异或值问题。压缩Trie(Patricia Trie)则在处理有大量相同前缀的情况时能够显著节省空间。

掌握Trie数据结构及其变种，将帮助你更有效地解决各类字符串相关问题。