Trie 字典树/前缀树 – 世子之争，素来如此

前缀树（Trie，又称字典树）是一种高效处理字符串的树形数据结构，适用于前缀匹配、自动补全、敏感词过滤等场景。

1. 核心思想

节点结构：每个节点存储子节点指针（如数组或哈希表）和结束标记（isEnd）。
路径共享：相同前缀的字符串共享路径，节省空间。
时间复杂度：插入和查询均为O(L)（L为字符串长度）。

2. C++实现代码

基础版本（支持小写字母）

#include <vector>
#include <string>
using namespace std;

class Trie {
private:
    struct TrieNode {
        vector<TrieNode*> children;
        bool isEnd;
        TrieNode() : children(26, nullptr), isEnd(false) {}
    };
    TrieNode* root;

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

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

    bool search(const string& word) {
        TrieNode* node = findNode(word);
        return node && node->isEnd;
    }

    bool startsWith(const string& prefix) {
        return findNode(prefix) != nullptr;
    }

private:
    TrieNode* findNode(const string& s) {
        TrieNode* node = root;
        for (char c : s) {
            int idx = c - 'a';
            if (!node->children[idx]) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

优化版本（支持任意字符，使用哈希表）

#include <unordered_map>
class Trie {
private:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd;
        TrieNode() : isEnd(false) {}
    };
    TrieNode* root;

public:
    // 方法同上，仅需修改字符处理逻辑
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }
    // search和startsWith方法类似调整
};

3. 功能扩展

统计前缀出现次数

struct TrieNode {
    int pass; // 经过该节点的字符串数
    int end;  // 以该节点结尾的字符串数
    // ...其他成员
};

void insert(const string& word) {
    TrieNode* node = root;
    node->pass++;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
        node->pass++;
    }
    node->end++;
}

int countPrefix(const string& prefix) {
    TrieNode* node = findNode(prefix);
    return node ? node->pass : 0;
}

删除操作

void remove(const string& word) {
    if (!search(word)) return;
    TrieNode* node = root;
    node->pass--;
    for (char c : word) {
        int idx = c - 'a';
        if (--node->children[idx]->pass == 0) {
            delete node->children[idx];
            node->children[idx] = nullptr;
            return;
        }
        node = node->children[idx];
    }
    node->end--;
}