当前位置：首页 > news >正文

leetcode 208. 实现 Trie (前缀树)

news 来源：原创 2025/7/14 1:30:09

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

请你实现 Trie 类：

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

基本做法：unordered_set<string>存储，前缀通过find实现

适用于单词长度较小

class Trie {
public:unordered_set<string> dp;Trie() {}void insert(string word) {if(!dp.count(word)){dp.insert(word);}}bool search(string word) {if(dp.count(word)){return true;}else return false;}bool startsWith(string prefix) {for(auto ie:dp){if(ie.find(prefix)==0){return true;}}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);*/

优点：插入，和查询的时间复杂度为O(1),内存占用小
缺点：多次前缀查询性能较低，时间复杂度为O(N*len) len为单词长度

26叉树实现

我们在Trie类种定义了一个26字母next表

适用于需要多次使用到前缀查询

字符插入

//当我们插入 apple对象时
当前Tire next全为空
第一个字符为a 
那我们 将next[0]创建好 
第二个字符 为p
那我们创建之前next[0]指向的next['p'-'a']
然后依次类推知道字符遍历完毕  我们就将这个字符插入到这个26叉数中 并且有利于前缀查询

void insert(string word) 
{auto temp=this;for(auto c:word){c-='a';if(!temp->next[c]) temp->next[c]=new Trie();temp=temp->next[c];}temp->is_end=true;     //记录当前位置是一个单词的尾  和前缀区分开来以便serach
}

查找辅助函数

Trie* find_(string prefix)
{auto temp=this;for(auto c:prefix){c-='a';if(temp->next[c]==nullptr)      //字符未遍历完但遇空 则表示没有相应的单词 {return nullptr;}temp=temp->next[c];}return temp;                       //返回prefix单词最后一个字符的next表
}

前缀查找prefix

找到前缀prefix 直接 return find_(predix)!=nullptr;

单词查找word

我们需要判断word最后一个字符的next表是否是单词尾部否则这个只是一个前缀而不是单词本身

return find_(word)!=nullptr&&find_(wrod)->is_end==true;

完整代码：

class Trie {
public:vector<Trie*> next;bool is_end;Trie():next(26,nullptr),is_end(false){}Trie* find_(string prefix){auto temp=this;for(auto c:prefix){c-='a';if(temp->next[c]==nullptr){return nullptr;}temp=temp->next[c];}return temp;}void insert(string word) {auto temp=this;for(auto c:word){c-='a';if(!temp->next[c]) temp->next[c]=new Trie();temp=temp->next[c];}temp->is_end=true;}bool search(string word) {return find_(word)&&find_(word)->is_end==true;}bool startsWith(string prefix) {return find_(prefix)!=nullptr;}
};/*** 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);*/

缺点：内存占用较高单词的每一个字符都有next表
优点：前缀查询快，单词查询较快，查询，插入时间复杂度均为O(len) len为单词长度

leetcode 208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。请你实现 Trie 类： Trie() 初始化前缀树对象…...

编程日记 2025/7/14 1:30:09

kafka进阶_3.消费消息

文章目录一、消费消息概览1.1、消费示例代码1.2、消费过程二、消费者组2.1、push & pull2.2、消费者组三、调度器Coordinator四、消费者分配策略4.1、引言4.2、分配基本流程4.3、分配策略4.3.1、轮询分配策略4.3.2、轮询分配策略五、消费偏移量5.1、起始偏移量5.2、指定…...

编程日记 2025/7/14 8:52:10

预测未来 | MATLAB实现Transformer时间序列预测未来

预测未来 | MATLAB实现Transformer时间序列预测未来预测效果基本介绍 1.Matlab实现Transformer时间序列预测未来； 2.运行环境Matlab2023b及以上，data为数据集，单变量时间序列预测； 3.递归预测未来数据，可以控制预…...

编程日记 2025/7/9 14:19:19

VirtualBox7.0.6安装配置

VirtualBox7.0.6安装配置提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加文章目录 VirtualBox7.0.6安装配置1.安装虚拟机1.1安装虚拟机的必要条件1.1.1开启虚拟化1.1.1.1检查虚拟化是否开启1.1.1.2 开启虚拟化 1.2 安装虚拟机1.1创建…...

编程日记 2025/7/13 16:35:49

Spring Boot英语知识分享网站：技术与实践

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。是基于SQL的客户/服务器模式的关系数据库管理系统，它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等，非常…...

编程日记 2025/7/12 18:03:02

HarmonyOS4+NEXT星河版入门与项目实战（22）------动画（属性动画与显示动画）

文章目录 1、属性动画图解2、案例实现-小鱼移动游戏1、代码实现2、代码解释3、资源图片4、实现效果3、显示动画4、案例修改-显示动画5、总结1、属性动画图解这里我们用一张完整的图来汇整属性动画的用法格式和使用的主要属性范围，如下所示： 2、案例实现-小鱼移动游戏 1、代…...

编程日记 2025/7/14 16:11:38

AI赋能公共服务转型升级 | 第十届中国行业互联网大会暨腾讯云TVP行业大使三周年庆典公共服务专场圆满举办！

引言党的二十大报告把“基本公共服务实现均等化”作为 2035 年我国发展的总体目标之一，强调要“健全基本公共服务体系，提高公共服务水平”。AI 作为新质生产力的核心驱动力之一，正在公共服务领域发挥着越来越重要的作用。 2024 年 10 月 2…...

编程日记 2025/7/14 6:28:46

网络基础 - 地址篇

一、IP 地址 IP 协议有两个版本，IPv4 和 IPv6IP 地址(IPv4 地址)是一个 4 字节，32 位的正整数，通常使用 “点分十进制” 的字符串进行表示，例如 192.168.0.1，用点分割的每一个数字表示一个字节，范围是 0 ~…...

编程日记 2025/7/14 16:16:18

chrome允许http网站打开摄像头和麦克风

第一步 chrome://flags/#unsafely-treat-insecure-origin-as-secure 第二步填入网址，点击启用第三步重启 Chrome：设置完成后，点击页面底部的 “Relaunch” 按钮，重新启动 Chrome 浏览器，使更改生效。...

编程日记 2025/7/3 14:04:02

uniapp前端开发,基于vue3,element plus组件库,以及axios通讯

简介 UniApp 是一个基于 Vue.js 的跨平台开发框架，旨在通过一次开发、编译后运行在多个平台上，如 iOS、Android、H5、以及小程序（微信小程序、支付宝小程序、百度小程序等）等。UniApp 为开发者提供了统一的开发体验，使…...

编程日记 2025/7/10 12:19:08

STM32-- 串口发送数据

while(USART_GetFlagStatus(USART2,USART_FLAG_TXE)RESET);？？ 答： 这行代码： while(USART_GetFlagStatus(USART2, USART_FLAG_TXE) RESET);的作用是等待串口 USART2 的发送数据寄存器（TXE，Transmit Dat…...

编程日记 2025/7/14 5:41:42

网络安全提示

如果您是企业主或 IT 经理，您应该知道计算机安全的重要性。从保护密码安全的基础知识到网络钓鱼、恶意软件等的危险，本文将为您提供您需要了解的有关网络安全的信息。每年，互联网都变得越来越大，这意味着我们为黑客和网络犯罪分…...

编程日记 2025/7/10 13:50:08

【计算机网络】多路转接之epoll

epoll也是一种linux中的多路转接方案(epoll也是只负责IO过程中的"等") 一、epoll相关接口的使用 1.epoll_create int epoll_create(int size); 功能：创建一个epoll模型 ① int size：没意义了 >0就行返回值：返回一个文件…...

编程日记 2025/7/8 7:45:26

nextjs+nestjs+prisma写todolist全栈项目

技术栈 nextjsnestjsprisma所学知识 Nextjs组件渲染，状态，路由docker启动Mysql容器prisma操作Mysql（CRUD）允许跨域请求APITanStack Query异步状态管理fetch api服务器组件预请求数据nestjs 管道和异常处理检测id是否正整数Docker启动Mysql容器 compose.yml name: todoLis…...

编程日记 2025/7/8 22:12:50

重构代码之将双向关联改为单向关联

在代码重构中，双向关联改为单向关联是指将原本双向关联转变为单向关联。这种重构方式有助于简化对象模型和提高代码的可维护性，减少不必要的耦合。下面是对这个重构技巧的详细讲解。一、为什么需要将双向关联改为单向关联？ 减少耦合&#…...

编程日记 2025/7/14 7:52:35

Linux介绍与安装指南：从入门到精通

1. Linux简介 1.1 什么是Linux？ Linux是一种基于Unix的操作系统，由Linus Torvalds于1991年首次发布。Linux的核心（Kernel）是开源的，允许任何人自由使用、修改和分发。Linux操作系统通常包括Linux内核、GNU工具集、图…...

编程日记 2025/7/13 8:42:08

深度学习中的正则化模型是什么意思？

一、定义在深度学习中，正则化是一种用于防止过拟合的技术。过拟合是指模型在训练数据上表现非常好，但在新的、未见过的数据（测试数据）上表现很差的情况。正则化模型就是通过在损失函数中添加额外的项来约束模型的复杂度&#xf…...

编程日记 2025/7/12 16:28:01

rabbitMq两种消费应答失败处理方式

在rabbitMq消费端，有三种应答模式： none：不处理。即消息投递给消费者后立刻 ack 消息会立刻从MQ删除。非常不安全，不建议使用 manual：手动模式。需要自己在业务代码中调用api，发送 ack 或 reject&#xff…...

编程日记 2025/7/8 16:47:39

windows C#-使用反射访问特性

你可以定义自定义特性并将其放入源代码中这一事实，在没有检索该信息并对其进行操作的方法的情况下将没有任何价值。通过使用反射，可以检索通过自定义特性定义的信息。主要方法是 GetCustomAttributes，它返回对象数组，这些对象在…...

编程日记 2025/7/14 8:40:30

java中链表的数据结构的理解

在 Java 中，链表是一种常见的数据结构，可以通过类的方式实现自定义链表。以下是关于 Java 中链表的数据结构和实现方式的详细介绍。 1. 自定义链表结构 Java 中链表通常由一个节点类 (ListNode) 和可能的链表操作类构成。节点类 (ListNode) 这是链表…...

编程日记 2025/7/11 13:54:47

ctfshow

1,web153 大小写绕过失败使用.user.ini 来构造后⻔ php.ini是php的⼀个全局配置⽂件，对整个web服务起作⽤；⽽.user.ini和.htaccess⼀样是⽬录的配置⽂件，.user.ini就是⽤户⾃定义的⼀个php.ini，我们可以利⽤这个⽂件来构造后⻔和…...

编程日记 2025/7/5 23:15:07

【AI绘画】Midjourney进阶：色调详解（下）

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: AI绘画 | Midjourney 文章目录 💯前言💯Midjourney中的色彩控制为什么要控制色彩？为什么要在Midjourney中控制色彩？ 💯色调纯色调灰色调暗色调 &#x1f4af…...

编程日记 2025/7/9 23:35:37

lanqiaoOJ 3747：繁忙的精神疗养院 ← STL queue

【题目来源】https://www.lanqiao.cn/problems/3747/learning/【题目描述】心灵之园是一家知名的精神疗养院，为了提供更优质的服务，他们专门设立了一个 VIP 诊室和一个普通诊室。VIP 诊室主要接待特殊需求的高级会员，而普通诊室则服务所有的…...

编程日记 2025/7/12 23:30:16

Local Changes不展示，DevEco Studio的git窗口中没有Local Changes

DevEco Studio的git窗口中，没有Local Changes，怎么设置可以调出？ 进入File-->Settings-->Version Control，将Use non-modal commit interface前的勾选框取消勾选，点击OK即可在打开git窗口，就可以看到…...

编程日记 2025/7/10 12:13:50

探索Python项目模板化的新纪元 —— Copier库揭秘

文章目录 **探索Python项目模板化的新纪元 —— Copier库揭秘**1. 背景介绍：为何Copier成为Python开发者的新宠？2. Copier究竟是什么？3. 如何安装Copier？4. 简单库函数使用方法创建模板从Git URL创建项目使用快捷方式动态文件生成…...

编程日记 2025/7/10 5:33:51

导入100道注会cpa题的方法，导入试题，自己刷题

一、问题描述复习备考的小伙伴们，往往希望能够利用零碎的时间和手上的试题，来复习和备考用一个能够导入自己试题的刷题工具，既能加强练习又能利用好零碎时间，是一个不错的解决方案目前市面上刷题工具存下这些问题 1、要收费…...

编程日记 2025/7/10 2:14:15

使用NAS开启无纸化办公，Docker部署开源文档管理系统『Paperless-ngx』

使用NAS开启无纸化办公，Docker部署开源文档管理系统『Paperless-ngx』哈喽小伙伴们好，我是Stark-C~ 对于文案类的办公场景来说，手头堆放最多的可能就是各种文档文件，以及各种用过的打印废纸。这么多年来，不管是领…...

编程日记 2025/7/9 22:58:04

1.拉取mysql镜像 docker pull mysql:5.7 2.启动mysql容器 docker run -d -e MYSQL_ROOT_PASSWORD123456 -e MYSQL_TCP_PORT3307 -p 3307:3307 -v /SDXL/wjz/docker_mysql_log:/var/log/mysql -v /SDXL/wjz/docker_mysql_data:/var/lib/mysql -v /SDXL/wjz/docker_mysql_conf:/e…...

编程日记 2025/7/10 0:54:53