前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【每日算法Day 84】面试必考题:Trie(字典树/前缀树)的实现

【每日算法Day 84】面试必考题:Trie(字典树/前缀树)的实现

作者头像
godweiyang
发布2020-04-02 11:38:34
1.2K0
发布2020-04-02 11:38:34
举报
文章被收录于专栏:算法码上来

题目链接

LeetCode 208. 实现 Trie (前缀树)[1]

题目描述

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例1

代码语言:javascript
复制
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 构成的。
  • 保证所有输入均为非空字符串。

题解

字典树主要支持插入字符串、查询字符串是否在字典树中、查询字典树中是否存在某个前缀等操作,我这里还额外实现了一下 c++ 版本的删除字符串操作。

初始化字典树

初始化的时候,根结点为空,不用来放任何字符,所有字符串都是从下一层子结点开始存储。

每个结点有 26 个指针,指向下一层子结点,每个指针代表着下一个不同的字母。

每个结点还保存了一个变量 isEnd ,用来表示该结点是不是某个字符串结束的位置。

插入字符串

从根结点往下递归,如果字符串中下一个字母对应的子结点为空,那就新建一个结点再递归,否则的话就直接递归下去。

最后把最后一个结点的 isEnd 设置为 1,表示这个结点是字符串的结束位置。

查询字符串

从根结点往下递归查找,如果字符串还没遍历结束,但是结点已经空了,说明字符串不在字典树中。否则的话一直查找到最后一个字符,然后看对应结点的 isEnd 是 1 还是 0,如果是 1 ,就存在字符串,否则不存在。

查询字符串前缀

和查询字符串过程一模一样,唯一的区别就是最后不用看最后一个结点的 isEnd 了,直接返回 true 。因为既然都查询到了最后一个字符了,说明这个前缀一定存在。

删除字符串

这个是我自己实现的,一般来说字典树很少用到删除操作。

首先整体框架是和查询字符串类似的,从根结点往下递归查询,然后用一个栈保存查询到的结点。

如果查询过程中直接遇到了空结点,就直接返回,因为都不存在字符串,就不用删除了。然后判断最后一个结点的类型。

如果它的 isEnd 是 0,说明字符串不存在,那就直接返回不用删了。

如果它不是叶子结点,说明后面还接着字符串呢,那也不用删了,只要把该结点的 isEnd 设置为 0 就行了。

否则的话它就是叶子结点,那么就直接删除这个结点,并且从栈里出栈。

然后从栈里最后一个结点开始删除,直到栈顶的结点不是叶子结点(表示字典树中存在删除字符串的相同前缀字符串)或者 isEnd 是 1(表示字典树中存在删除字符串的前缀子串)。

代码

具体实现上面,c++ 我采用的结构体指针来构建出了一颗树。而 python 我直接用的嵌套的字典,并没有真正的构建出树,只有一个类,这样还挺方便的,但是删除操作有点麻烦,暂时就不写了。

c++

代码语言:javascript
复制
class Trie {
public:
    bool isEnd;
    vector<Trie*> next;

    Trie() {
        isEnd = false;
        next = vector<Trie*>(26, 0);
    }

    ~Trie() {
        for (auto p : next) delete p;
    }
    
    void insert(string word) {
        Trie* node = this;
        for (auto c : word) {
            if (node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }

    void del(string word) {
        stack<Trie*> st;
        Trie* node = this;
        for (auto c : word) {
            node = node->next[c-'a'];
            st.push(node);
            if (node == NULL) return;
        }
        if (!(node->isEnd)) return;
        if (!isLeaf(node)) {
            node->isEnd = false;
            return;
        }
        delete node;
        st.pop();
        while (!st.empty()) {
            node = st.top();
            st.pop();
            if (isLeaf(node) && !(node->isEnd)) delete node;
            else break;
        }
    }
    
    bool search(string word) {
        Trie* node = this;
        for (auto c : word) {
            node = node->next[c-'a'];
            if (node == NULL) return false;
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for (auto c : prefix) {
            node = node->next[c-'a'];
            if (node == NULL) return false;
        }
        return true;
    }

    bool isLeaf(Trie* node) {
        for (auto p : next) {
            if (p) return false;
        }
        return true;
    }
};

python

代码语言:javascript
复制
class Trie:
    def __init__(self):
        self.nxt = {}

    def insert(self, word: str) -> None:
        node = self.nxt
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['#'] = True

    def search(self, word: str) -> bool:
        node = self.nxt
        for c in word:
            if c not in node:
                return False
            node = node[c]
        return '#' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.nxt
        for c in prefix:
            if c not in node:
                return False
            node = node[c]
        return True

参考资料

[1]

LeetCode 208. 实现 Trie (前缀树): https://leetcode-cn.com/problems/implement-trie-prefix-tree/

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接
  • 题目描述
  • 题解
    • 初始化字典树
      • 插入字符串
        • 查询字符串
          • 查询字符串前缀
            • 删除字符串
            • 代码
              • c++
                • python
                  • 参考资料
                  相关产品与服务
                  NLP 服务
                  NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
                  领券
                  问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档