从零开始理解 Trie 树:高效字符串存储与查找的利器【自动补全、拼写检查】
题目分析
这道题让我们实现一个 Trie 类(也称为前缀树),以便高效地插入和查询字符串。前缀树是一种特殊的树形数据结构,适用于快速存储和检索字符串数据集中的键,比如实现 自动补全 和 拼写检查。
题目要求
Trie 类中有以下几个方法:
Trie()
: 初始化前缀树对象。insert(String word)
: 向前缀树中插入一个字符串word
。search(String word)
: 如果前缀树中包含word
,返回true
;否则,返回false
。startsWith(String prefix)
: 如果前缀树中存在以prefix
为前缀的字符串,则返回true
;否则,返回false
。
解题思路
为了解决这个问题,我们可以按照以下步骤来思考:
-
Trie 数据结构:前缀树用来存储字符串,字符间的共享前缀会共用路径,以减少空间消耗并提高查询效率。每个节点代表一个字符,树的根节点为空节点。沿着从根节点出发的路径到叶节点的字符组合表示存储的字符串。
-
TrieNode 类设计:前缀树中的每个节点可以使用一个
TrieNode
类来表示。每个TrieNode
保存两个信息:- 子节点列表:存储连接到当前节点的其他字符。
- 结束标志:用于标记当前节点是否是一个单词的结尾。
-
Trie 类设计:前缀树本身实现插入、查找和前缀匹配等功能。需要在
Trie
类中实现以下方法:- 插入(insert):从根节点开始,逐字符插入,如果字符节点不存在就创建新节点,最后一个字符节点标记为单词结尾。
- 查找(search):从根节点出发,逐字符查找,直到找到整个单词或发现单词不存在。
- 前缀匹配(startsWith):类似查找,只需检查前缀是否存在即可。
实现代码
以下是 Trie 类的 C++ 实现,包含插入、查找和前缀匹配功能。
#include <iostream>
#include <unordered_map>
#include <string>class TrieNode {
public:bool isEndOfWord; // 标记当前节点是否为一个单词的结尾std::unordered_map<char, TrieNode*> children; // 用于存储子节点TrieNode() : isEndOfWord(false) {} // 构造函数初始化
};class Trie {
private:TrieNode* root;public:Trie() {root = new TrieNode(); // 初始化 Trie,根节点为空节点}// 插入字符串void insert(const std::string& word) {TrieNode* node = root;for (char ch : word) {if (node->children.find(ch) == node->children.end()) {node->children[ch] = new TrieNode(); // 如果子节点不存在,则创建}node = node->children[ch]; // 移动到下一个子节点}node->isEndOfWord = true; // 最后一个节点标记为单词结尾}// 查找字符串bool search(const std::string& word) const {TrieNode* node = root;for (char ch : word) {if (node->children.find(ch) == node->children.end()) {return false; // 如果字符节点不存在,返回 false}node = node->children[ch]; // 移动到下一个子节点}return node->isEndOfWord; // 判断是否为单词结尾}// 查找前缀bool startsWith(const std::string& prefix) const {TrieNode* node = root;for (char ch : prefix) {if (node->children.find(ch) == node->children.end()) {return false; // 如果前缀节点不存在,返回 false}node = node->children[ch]; // 移动到下一个子节点}return true; // 所有字符都找到,返回 true}
};
示例讲解
假设我们运行以下代码:
Trie trie = Trie();
trie.insert("apple");
std::cout << trie.search("apple") << std::endl; // 返回 true
std::cout << trie.search("app") << std::endl; // 返回 false
std::cout << trie.startsWith("app") << std::endl; // 返回 true
trie.insert("app");
std::cout << trie.search("app") << std::endl; // 返回 true
执行步骤
为了更具象地展示前缀树的构建过程,我们可以用图形化的方式模拟每一步的节点构造。
1. 初始化 Trie
Trie trie = Trie();
- 创建了一个
Trie
对象。此时只有一个根节点,根节点本身是空的,不保存任何字符内容。
2. 插入字符串 "apple"
trie.insert("apple");
在插入 "apple"
时,前缀树会按字符逐个插入:a -> p -> p -> l -> e
。详细步骤如下:
-
第一步:根节点开始插入字符
'a'
。根节点没有子节点'a'
,于是创建一个节点表示'a'
并加入子节点。(root)|a
-
第二步:在
'a'
节点下插入字符'p'
。节点'a'
没有子节点'p'
,创建并添加节点表示'p'
。(root)|a|p
-
第三步:继续在
'p'
节点下插入字符'p'
。节点'p'
没有子节点'p'
,创建并添加节点表示'p'
。(root)|a|p|p
-
第四步:继续在第二个
'p'
节点下插入字符'l'
。节点'p'
没有子节点'l'
,创建并添加节点表示'l'
。(root)|a|p|p|l
-
第五步:在
'l'
节点下插入字符'e'
。节点'l'
没有子节点'e'
,创建并添加节点表示'e'
,并将其标记为单词结尾 (isEndOfWord = true
)。(root)|a|p|p|l|e (end)
到此为止,我们已经成功将 "apple"
插入到了前缀树中。"apple"
的路径为:a -> p -> p -> l -> e
。
3. 查找 "apple"
trie.search("apple");
- 从根节点逐字符查找
a -> p -> p -> l -> e
。 - 遇到节点
'e'
,并且'e'
被标记为单词的结尾 (isEndOfWord = true
),因此返回true
。
4. 查找 "app"
trie.search("app");
- 从根节点逐字符查找
a -> p -> p
。 - 到达最后一个
p
节点,但它没有被标记为单词的结尾(isEndOfWord = false
),表示"app"
虽然存在路径,但不是一个完整的单词,因此返回false
。
5. 查找前缀 "app"
trie.startsWith("app");
- 从根节点逐字符查找
a -> p -> p
。 - 找到
"app"
路径中的所有字符,所以返回true
表示"app"
是某个单词的前缀。
6. 插入 "app"
trie.insert("app");
这次插入 "app"
的过程如下:
-
从根节点逐字符插入
a -> p -> p
。 -
到达最后一个
p
节点,因为节点已存在,无需再创建节点。只需将该节点标记为单词结尾 (isEndOfWord = true
)。(root)|a|p|p (end)|l|e (end)
现在 "app"
路径已标记为一个完整的单词。
7. 查找 "app"
再次验证
trie.search("app");
- 从根节点逐字符查找
a -> p -> p
。 - 找到
p
节点,且p
已标记为单词的结尾 (isEndOfWord = true
),因此返回true
表示"app"
存在。
图示总结
通过逐字符的插入和标记,我们最终得到了如下的前缀树结构:
(root)|a|p|p (end)|l|e (end)
"app"
是一条有效路径,以p (end)
为结尾。"apple"
是另一条有效路径,以e (end)
为结尾。
小结
- 插入过程:逐字符插入,每次检查是否存在子节点,不存在则创建。单词结尾的字符节点会被标记为
isEndOfWord = true
。 - 查找过程:逐字符查找,直到找到整个单词路径。如果路径末尾的节点标记为单词结尾,则该单词存在。
- 前缀查找:逐字符查找路径中的前缀,只需验证路径存在,不要求路径末尾节点为单词结尾。
这种树形结构使得共享前缀的单词复用相同路径,节省存储空间并提高了查询效率。
复杂度分析
- 时间复杂度:
- 插入:O(m),其中 m 为字符串的长度。
- 查找:O(m)。
- 前缀查找:O(m)。
- 空间复杂度:插入 N 个字符串,每个长度为 m,最坏情况下空间复杂度为 O(N * m),但由于前缀共享,这个复杂度会降低。
好的,让我们通过更加通俗、易于理解的语言来解释 自动补全 和 拼写检查 的实现过程,便于大家理解。
应用场景
自动补全和拼写检查是前缀树(Trie)的两个经典应用,它们都需要在大量单词中快速查找具有相同前缀或类似拼写的单词。前缀树的结构使得这些功能可以在短时间内完成。
1. 自动补全
自动补全主要用于在用户输入一部分单词(前缀)时,推荐以该前缀开头的完整单词。例如,当用户输入 "app"
时,系统希望能迅速推荐像 "apple"
、"application"
这样的词。
自动补全的步骤:
-
第一步:查找前缀
通过startsWith
方法,从根节点开始,按用户输入的前缀逐字符向下查找。如果每个字符都能在前缀树中找到,说明该前缀存在;否则,表示 Trie 中没有以该前缀开头的单词。 -
第二步:找出所有可能的单词
一旦找到前缀的最后一个字符节点,接下来就是从这个节点开始,通过深度优先遍历(DFS)或广度优先遍历(BFS)找到所有以这个前缀开头的单词。在遍历过程中,只要遇到节点被标记为一个完整单词的结尾,就可以将当前路径组合成一个单词,加入到推荐结果中。
示例:
假设前缀树中存有 "apple"
、"app"
、"application"
、"apply"
等单词。当用户输入 "app"
时,系统将:
- 使用
startsWith
方法查找前缀"app"
,确认前缀存在。 - 从最后的
"p"
节点开始,遍历其子节点,逐一找到以"app"
开头的完整单词:"apple"
、"application"
和"apply"
。
这就是自动补全的基本过程,最终返回以 "app"
为开头的推荐单词。
2. 拼写检查
拼写检查用于纠正用户的拼写错误。当用户输入单词时,如果单词不存在,拼写检查会推荐一些拼写相似的正确单词。这里使用前缀树来检查是否存在某个单词,并生成近似的拼写推荐。
拼写检查的步骤:
-
第一步:检查单词是否存在
使用search
方法,直接在前缀树中查找用户输入的单词。如果找到,说明拼写正确;如果找不到,则需要生成拼写相似的候选词。 -
第二步:生成近似候选词
如果单词不存在,我们就使用一些简单的修改方式生成可能的“拼写相近”的词,然后逐一在前缀树中查找,看看哪些单词存在。常用的修改方式包括:- 替换字符:将单词中的某个字母替换为其他字母,生成新单词并查找。例如,将
"appl"
中的最后一个字符替换为"e"
,生成"apple"
。 - 删除字符:尝试删除单词的某个字符,生成新单词并查找。例如,删除
"appl"
中的最后一个字符生成"app"
。 - 添加字符:尝试在某个位置插入一个新字符,生成新单词并查找。例如,在
"appl"
后添加"e"
,生成"apple"
。 - 交换字符:尝试交换单词中的相邻字符,生成新单词并查找。
- 替换字符:将单词中的某个字母替换为其他字母,生成新单词并查找。例如,将
示例:
假设用户输入了 "appl"
(少了一个字母 e
)。Trie 会先尝试直接查找 "appl"
,发现不存在,然后生成近似词进行查找:
- 尝试添加字符
"e"
,生成"apple"
,在 Trie 中找到了该单词。 - 也可以通过删除字符生成
"app"
,在 Trie 中也存在。
最终,拼写检查可以将 "apple"
和 "app"
作为拼写建议返回给用户。
总结
这道题中的 Trie 数据结构为我们提供了一种快速存储和查询大量字符串的方法,特别适合具有公共前缀的字符串。通过这种数据结构,可以高效地完成自动补全、拼写检查等操作。在实现过程中,我们使用了 TrieNode
和 Trie
类分别表示节点和整个前缀树,采用 unordered_map
存储子节点关系,实现了 O(m) 时间复杂度的插入和查找功能。
相关文章:
从零开始理解 Trie 树:高效字符串存储与查找的利器【自动补全、拼写检查】
题目分析 这道题让我们实现一个 Trie 类(也称为前缀树),以便高效地插入和查询字符串。前缀树是一种特殊的树形数据结构,适用于快速存储和检索字符串数据集中的键,比如实现 自动补全 和 拼写检查。 题目要求 Trie 类…...
关于sse、websocket与流式渲染
一、SSE是什么? 网络中的 SSE (Server-Sent Events) 是一种服务器向浏览器单向推送数据的机制,常用于需要实时更新的数据传输,如新闻推送、股票行情、聊天应用等。 SSE 的特点: 单向通信:服务器向客户端推送数据&…...
Python 语法与数据类型详解
Python 语法与数据类型详解 Python 以其简洁易读的语法和丰富多样的数据类型在编程领域占据重要地位。深入理解 Python 的语法和数据类型是掌握这门语言的关键。 一、Python 语法概述 (一)缩进规则 Python 独特的缩进规则是其语法的重要特征之一。与…...
LeetCode题练习与总结:扁平化嵌套列表迭代器--341
一、题目描述 给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数,要么是一个列表;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化,使之能够遍历这个列表中的所有整数。 实现扁平迭代器类 NestedIterato…...
51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25
51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25 声明:本文图片来源于网络 A模拟信号特点: 电压或者电流 缓慢上升 随着时间连续缓慢上升或下降 D数字信号特点:电压或者电流 保持一段时间的高/低电平 状态 / 突变 (高电压瞬间低电压) 数字电路中 通常将0-1v电压称…...
Typora 、 Minio and PicGo 图床搭建
流程介绍 本地安装Typora笔记工具拥有一台装有docker的服务器配置minio云图床管理控制页面下载PicGo上传工具服务器Docker环境搭建—Ubuntu系统 删除旧docker的所有依赖(非root用户) # 删除docker及安装时自动安装的所有包 sudo apt-get autoremove docker docker-ce docker…...
【计网】UDP Echo Server与Client实战:从零开始构建简单通信回显程序
目录 前言: 1.实现udpserver类 1.1.创建udp socket 套接字 --- 必须要做的 socket()讲解 代码实现:编辑 代码讲解: 1.2.填充sockaddr_in结构 代码实现: 代码解析: 1.3.bind sockfd和…...
微服务网关Zuul
一、Zuul简介 Zuul是Netflix开源的微服务网关,包含对请求的路由和过滤两个主要功能。 1)路由功能:负责将外部请求转发到具体的微服务实例上,是实现外部访问统一入口的基础。 2)过滤功能:负责对请求的过程…...
BuildCTF线上赛WP
Build::CTF flag不到啊战队--WP 萌新战队,还请多多指教~ 目录 Build::CTF flag不到啊战队--WP Web ez!http find-the-id Pwn 我要成为沙威玛传奇 Misc what is this? 一念愚即般若绝,一念智即般若生 别真给我开盒了哥 四妹,你听…...
《使用Gin框架构建分布式应用》阅读笔记:p143-p207
《用Gin框架构建分布式应用》学习第10天,p143-p207总结,总计65页。 一、技术总结 1.auth0 本人实际工作中未遇到过,mark一下,参考:https://auth0.com/。 2.使用template (1)c.File() (2)router.Static() (3)rou…...
华为网络管理配置实例
目录 组网需求 数据规划 配置思路 操作步骤 结果验证 配置脚本 管理员可以通过eSight网管系统对FW进行监控和管理,接收FW的告警。 组网需求 如图1所示,某企业在网络边界处部署了FW作为安全网关,并部署了eSight网管系统对网络设备进行集中…...
大语言模型数据处理方法(基于llama模型)
文章目录 前言一、基于huggingface的DataCollatorForSeq2Seq方法解读1、DataCollatorForSeq2Seq方法2、batch最长序列填充3、指定长度填充二、构建大语言模型数据加工模块1、数据读取2、数据加工1、数据格式2、预训练(pretrain)数据加工3、微调(sft)数据加工①、sft数据加工…...
爱奇艺大数据多 AZ 统一调度架构
01# 导语 爱奇艺大数据技术广泛应用于运营决策、用户增长、广告分发、视频推荐、搜索、会员营销等场景,为公司的业务增长和用户体验提供了重要的数据驱动引擎。 多年来,随着公司业务的发展,爱奇艺大数据平台已积累了海量数据,这…...
【C++篇】栈的层叠与队列的流动:在 STL 的韵律中探寻数据结构的优雅之舞
文章目录 C 栈与队列详解:基础与进阶应用前言第一章:栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章:队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.…...
使用 Flask 实现简单的登录注册功能
目录 1. 引言 2. 环境准备 3. 数据库设置 4. Flask 应用基本配置 5. 实现用户注册 6. 实现用户登录 7. 路由配置 8. 创建前端页面 9. 结论 1. 引言 在这篇文章中,我们将使用 Flask 框架创建一个简单的登录和注册系统。Flask 是一个轻量级的 Python Web 框架…...
计算机毕业设计Python+大模型微博情感分析 微博舆情预测 微博爬虫 微博大数据 舆情分析系统 大数据毕业设计 NLP文本分类 机器学习 深度学习 AI
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 《Python大模型微博情感分析…...
CTF--Misc题型小结
(萌新笔记,多多关照,不足之处请及时提出。) 不定时更新~ 目录 密码学相关 文件类型判断 file命令 文件头类型 strings读取 隐写术 尺寸修改 文件头等缺失 EXIF隐写 thumbnail 隐写 文件分离&提取 binwalk foremo…...
深度学习系列——RNN/LSTM/GRU,seq2seq/attention机制
1、RNN/LSTM/GRU可参考: https://zhuanlan.zhihu.com/p/636756912 (1)对于这里面RNN的表示中,使用了输入x和h的拼接描述,其他公式中也是如此 (2)各符号图含义如下 2、关于RNN细节,…...
通过call指令来学习指令摘要表的细节
E8 cw cw 表示E8后面跟随2 字节 (什么数不知道) rel16 指在与指令同一代码段内的相对地址偏移 D ,指向Instruction Operand Encoding 表中的D列, 他告诉我们 操作数1 是一个0FFSET N.S. 在64位模式下,某些指令需要使用“地址覆盖前缀”(address over…...
10分钟使用Strapi(无头CMS)生成基于Node.js的API接口,告别繁琐开发,保姆级教程,持续更新中。
一、什么是Strapi? Strapi 是一个开源的无头(headless) CMS,开发者可以自由选择他们喜欢的开发工具和框架,内容编辑人员使用自有的应用程序来管理和分发他们的内容。得益于插件系统,Strapi 是一个灵活的 C…...
创建插件 DLL 项目
Step 1: 创建插件 DLL 项目 在 Visual Studio 中创建一个新的 DLL 项目,并添加以下文件和代码。 头文件:CShapeBase.h cpp 复制代码 #pragma once #include <afxwin.h> // MFC 必需头文件 #include <string> #include <vector> #i…...
OpenCV双目相机外参标定C++
基于OpenCV库实现双目测量系统外参标定过程。通过分析双目测量系统左右相机拍摄的棋盘格标定板图像,包括角点检测、立体标定、立体校正和畸变校正的步骤,获取左右相机的相对位置关系和姿态。 a.检测每张图像中的棋盘格角点,并进行亚像素级精…...
【GESP】C++一级练习BCQM3055,4位数间隔输出
一级知识点取余、整除运算和格式化输出知识点应用。其实也可以用string去处理,那就属于GESP三级的知识点范畴了,孩子暂未涉及。 题目题解详见:https://www.coderli.com/gesp-1-bcqm3055/ https://www.coderli.com/gesp-1-bcqm3055/https://w…...
纯血鸿蒙的最难时刻才开始
关注卢松松,会经常给你分享一些我的经验和观点。 纯血鸿蒙(HarmonyOS NEXT)也正式发布了,绝对是一个历史性时刻,但最难的鸿蒙第二个阶段,也就是生态圈的建设,才刚刚开始。 目前,我劝你现在不要升级到鸿蒙…...
记一个mysql的坑
数据库表user, 存在一个name字段,字段为varchar类型 现在user表有这么两条记录: idnameageclass1NULL18一班2lisi20二班 假如我根据下面这一条件去更新,更新成功数据行显示为0 update user set age 19 where age 18 and class “一班”…...
Java中的设计模式:单例模式详解
摘要 单例模式(Singleton Pattern)是Java中最常用的设计模式之一,属于创建型模式。它的主要目的是确保一个类在系统中只有一个实例,并提供一个全局访问点来访问该实例。 1. 单例模式的定义 单例模式确保一个类只有一个实例&…...
NanoTrack原理与转tensorrt推理
文章目录 前言一、NanoTrack 工作原理二、运行demo与转换tensorrt模型2.1 运行pt模型demo2.2 转onnx模型2.3 转tensorrt模型2.4 运行trt模型推理 三、推理速度对比总结 前言 NanoTrack 是一种轻量级且高效的目标跟踪算法,基于Siamese网络架构,旨在在资源…...
YOLO11改进 | 卷积模块 | 卷积模块替换为选择性内核SKConv【附完整代码一键运行】
秋招面试专栏推荐 :深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 💡💡💡本专栏所有程序均经过测试,可成功执行💡💡💡 本文给大家带来的教程是将YOLO11的卷积替…...
CentOS进入单用户模式进行密码重置
一、单用户模式介绍 单用户模式是一种特殊的启动模式,主要用于系统维护和故障排除。在单用户模式下,系统以最小化的状态启动,只有最基本的系统服务会被加载,通常只有root用户可以登录。这种模式提供了对系统的完全控制࿰…...
bitpoke- mysql-operator cluster
sidecar版本只支持到8.0.35,35可以支持到mysql8.0.35 . 默认镜像是5.7的。需要自己打sidecar的镜像: # Docker image for sidecar containers # https://github.com/bitpoke/mysql-operator/tree/master/images/mysql-operator-sidecar-8.0 # 参考5…...
网站改版的方式/如何制作小程序
最近工作需要从Oracle迁移大量数据到MySql,由于涉及不深,便网上学习了很多的方法,现总结Oracle迁移大量数据到MySql如下:一,牛人编写的Oracle到MySQL的数据迁移工具从Oracle迁移数据到MySQL的小程序,ora2mysql下载地址…...
需要企业网站开发/win7优化
rsh配置&无密码登陆今天才知道我们有一个机器用的是rsh不是ssh(囧),还突然连不上了。就研究了一下,在网上插了好多文章,撞墙好多次终于成功了。现在发布研究结论。步骤如下:1. 安装rsh:#yum…...
专门做淘宝客网站/ip域名查询网
matlab 2011b中的函数cvexShowMatches()显示匹配图像是非常不爽。 执行如下代码: I1 imread(cameraman.tif);I2 imresize(imrotate(I1,-20), 1.2); points1 detectSURFFeatures(I1,MetricThreshold,10000);points2 detectSURFFeatures(I2,MetricThreshold,10000…...
什么网站做装修的/链接买卖
前言 在微服务实战:基于Spring Cloud Gateway AWS Cognito 的BFF案例一文中, 介绍了基于Amazon Cognito的OAuth授权码模式的认证流程。本文中,我们将研究可能针对此流程的恶意攻击以及如何防止它们。你将了解如何使用状态随机数(…...
做网站是否需要自购服务器/软文范例100例
# 前言什么是死锁?死锁有什么危害和特点?代码实现一个必然死锁的示例分析死锁的过程# 项目环境jdk 1.8github 地址:https://github.com/huajiexiewenfeng/java-concurrent本章模块:deadlock1.什么是死锁?关键词&#x…...
无锡网站制作公司/李飞seo
原博文 2017-05-17 12:04 − 在pycharm中的Python代码运行会出现各种奇葩的问题,比如,密码输入时不显示或没有提示,给我们带来一些麻烦,下面介绍几种代码运行的几种方式: 一、直接运行(Run按钮或者快捷键sh…...