力扣每日一题208:实现 Trie (前缀树)

2024-04-30 04:20

本文主要是介绍力扣每日一题208:实现 Trie (前缀树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目内容

难度 中等

Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

请你实现 Trie 类:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。

示例:

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]解释
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

提示:

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insertsearch 和 startsWith 调用次数 总计 不超过 3 * 104 次

面试中遇到过这道题?

1/5

通过次数

326.7K

提交次数

454K

通过率

72.0%

题目提供的结构(c++)

class Trie {
public:Trie() {}void insert(string word) {}bool search(string word) {}bool startsWith(string prefix) {}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

思路

首先很多人还不知道前缀树。

简单说来就是,根节点不存放数据,其它节点每个节点存放一个字母。从根节点到某个节点形成的路径就是一个单词。每一个非根节点会有个标记,记录以该节点为尾的路径是不是一个单词。

首先每个节点的数据结构一定要有结束标志和表示孩子节点的数据(我用的是哈希表,键对应的是孩子节点的字符,值对应的是孩子节点的地址)。
其次还可以添加代表该节点的字母(我用哈希表表示孩子节点,所以可以通过父节点来找到当前节点的字母。如果不能通过父节点来表示当前节点的字母,那么一定要有个变量能专门表示当前节点的字母),根节点走到当前节点的值,根节点到当前节点的距离等等。
随后就是根据前缀树的特点来模拟。其中我认为最核心的算法就是以下部分。

int n=word.length();
Node* cur=root;
int i=0;
while( i<n&&(cur->child).find(word[i])!=(cur->child).end() ){cur=(cur->child)[word[i]];i++;
}

上述代码走完后 :
i会指向word中最后一个匹配成功的后一个位置
cur会指向前缀树中最后一个匹配成功的地址。
随后就很方便的进行插入,查找,找到前缀操作。

复杂度
时间复杂度:

添加和查找时间复杂度,: O(m)O(m)O(m)
其中m为word的长度
查找前缀的时间复杂度: O(p)O(p)O(p)
p为前缀的长度

空间复杂度:

空间复杂度为单词的总长度: O(numberofwords∗averagewordlength)

实现代码

class Trie {
public:struct Node{bool flag=false;        //结束标志,true代表是结束char letter;         //该节点代表的字母unordered_map<char,Node*> child;string val;         //根走到当前节点的值Node() {};Node(char c) : letter(c) {};};Node* root;Trie() {root=new Node('#');}void insert(string word) {int n=word.length();Node* cur=root;int i=0;while( i<n&&(cur->child).find(word[i])!=(cur->child).end() ){cur=(cur->child)[word[i]];i++;}//word已经存在的情况if(i==n&&(cur->flag)==true){return;}else if(i==n&&(cur->flag)==false){//word在前缀树中但是不存在的情况cur->flag=true;}else if(i!=n){while(i<n){(cur->child)[word[i]]=new Node(word[i]);cur=(cur->child)[word[i]];i++;}(cur->flag)=true;//标志结束}//}bool search(string word) {int n=word.length();int i=0;            //word中最后一个匹配成功的后一个位置Node* cur=root;     //前缀树中匹配成功的最后一个位置while( i<n&&(cur->child).find(word[i])!=(cur->child).end() ){cur=(cur->child)[word[i]];i++;}if(i==n&&(cur->flag)==true ) return true;else return false;}bool startsWith(string prefix) {int n=prefix.length();int i=0;Node* cur=root;while( i<n&&(cur->child).find(prefix[i])!=(cur->child).end() ){cur=(cur->child)[prefix[i]];i++;}if( i==n&&(cur->flag==true||(cur->child).size()!=0) ) return true;else return false;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

这篇关于力扣每日一题208:实现 Trie (前缀树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/947895

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机