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

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

题目链接

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

题目描述

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

示例1

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++

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

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
相关文章
|
4月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
37 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
93 2
|
3月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
70 2
|
3月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
4月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
|
4月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看

热门文章

最新文章