大厂面试必考——字典树（前缀树）及其C++实现

字典树

字典树（trie）也称为前缀树，它其实是一种k叉树。一般用来在一组字符串中快速定位某个字符串，如下图中，可以在["bear", "bell", "bid", "bull", "buy", "sell", "stock", "stop"]这一组字符串中快速定位其中一个字符串，时间复杂度只需要$O(l)$，其中$l$是指定位字符串的长度，相比于遍历小了很多。

当然，字典树除了字符串这种典型应用，也可以应用于其他情况。

字典树这种数据结构，在大厂面试中经常被考到。比如在leetcode 208. 实现 Trie (前缀树)的评论区中就有不少人分享经验：

字典树的C++实现

字典树的实现也不算困难，关键是插入和查找两个接口。

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;
    Trie* searchPrefix(string prefix) {
        Trie* p = this;
        for(char c : prefix) {
            int idx = c - 'a';
            if(p->children[idx] == nullptr) {
                return nullptr;
            }
            p = p->children[idx];
        }
        return p;
    }
public:
    // 初始化
    Trie():isEnd(false) {
        this->children = vector<Trie*> (26, nullptr);
    }
    // 析构函数
    ~Trie() {
        for(int i = 0;i < 26;++i) {
            if(this->children[i] != nullptr) {
                delete this->children[i];
            }
        }
    }
    
    // 插入接口
    void insert(string word) {
        Trie* p = this;
        for(char c : word) {
            int idx = c - 'a';
            if(p->children[idx] == nullptr) {
                p->children[idx] = new Trie();
            }
            p = p->children[idx];
        }
        p->isEnd = true;
    }
    
    // 查找接口
    bool search(string word) {
        Trie* resNode = searchPrefix(word);
        return resNode && resNode->isEnd;
    }
    
    bool startsWith(string prefix) {
        return searchPrefix(prefix) != nullptr;
    }
};

关于内存管理

需要注意的是，用C++实现时会涉及到内存管理的问题，也经常被考查到，比如208题目的评论区中就有这样的分享：

那么什么时候需要主动释放内存呢？

我们知道，在程序运行时动态分配的内存是存储在堆中的，需要我们手动管理。
简单概括的话，就是手动分配的内存要手动释放，否则容易造成内存泄露。

以vector为例，如果不是通过new方式创建的，vector本身的实现会负责内存的创建和释放；而如果是使用new方式创建的vector，就需要手动通过delete删除。通过malloc分配的内存也需要通过free释放。

所以，在我们上面的实现中，需要手动释放通过new分配的内存。

字典树相关题目

除了直接的字典树实现题目208. 实现 Trie (前缀树)，
2707. 字符串中的额外字符、1803. 统计异或值在范围内的数对有多少和472. 连接词也与字典树相关。