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

发布时间:2024年01月09日

字典树

字典树trie)也称为前缀树,它其实是一种k叉树。一般用来在一组字符串中快速定位某个字符串,如下图中,可以在["bear", "bell", "bid", "bull", "buy", "sell", "stock", "stop"]这一组字符串中快速定位其中一个字符串,时间复杂度只需要 O ( l ) O(l) O(l),其中 l 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. 连接词也与字典树相关。

文章来源:https://blog.csdn.net/csdnofhaner/article/details/135483984
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。