前缀树(字典树/Trie) -----Java实现
目录
一.前缀树
1.什么是前缀树
2.前缀树的举例
二.前缀树的实现
1.前缀树的数据结构
1.插入字符串
2.查找字符串
3.查找前缀
三.词典中最长的单词
1.题目描述
2.问题分析
3.代码实现
一.前缀树
1.什么是前缀树
字典树(Trie树)是一种树形数据结构,常用于字符串的存储和查找。字典树的核心思想是利用字符串之间的公共前缀来节省存储空间和提高查询效率。它是一棵多叉树,每个节点代表一个字符串的前缀,从根节点到叶子节点的路径组成一个字符串。
字典树的根节点不包含字符,每个子节点代表一个字符,从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串,通常使用一个标志来标记一个节点代表的字符串是否存在。当需要在一组字符串中查找某个字符串时,可以利用字典树来实现高效的查找操作。
2.前缀树的举例
例如对字符串数组{"goog","google","bai","baidu","a"}建立前缀树,此时我们可以很清晰的看到前缀树的一些特征:
- 根结点不保存字符
- 前缀树是一颗多叉树
- 前缀树的每个节点保存一个字符
- 具有相同前缀的字符串保存在同一条路径上
- 字符串的尾处相应的在前缀树上也有结束的标志

二.前缀树的实现
力扣上的208题就是实现前缀树:力扣
1.前缀树的数据结构
在写代码的时候,我偏向于用哈希表来存储结点的信息,有的也可以用数组来存储结点的信息,本质上都是一样的
public class Trie {Map<Character, Trie> next;boolean isEnd;public Trie() {this.next = new HashMap<>();this.isEnd = false;}public void insert(String word) {}public boolean search(String word) {return false;}public boolean startsWith(String prefix) {return false;}
}
1.插入字符串
public void insert(String word) {Trie trie = this;//获得根结点for (char c : word.toCharArray()) {if (trie.next.get(c) == null) {//当前结点不存在trie.next.put(c, new Trie());//创建当前结点}trie = trie.next.get(c);//得到字符c的结点,继续向下遍历}trie.isEnd = true;}
2.查找字符串
public boolean search(String word) {Trie trie = this;//获得根结点for (char c : word.toCharArray()) {if (trie.next.get(c) == null) {//当前结点不存在return false;}trie = trie.next.get(c);//得到字符c的结点,继续向下遍历}return trie.isEnd;}
3.查找前缀
public boolean startsWith(String prefix) {Trie trie = this;//获得根结点for (char c : prefix.toCharArray()) {if (trie.next.get(c) == null) {//当前结点不存在return false;}trie = trie.next.get(c);//得到字符c的结点,继续向下遍历}return true;}
接下来是力扣上关于前缀树的一些题目
三.词典中最长的单词
1.题目描述
给出一个字符串数组
words组成的一本英语词典。返回words中最长的一个单词,该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案,则返回答案中字典序最小的单词。若无答案,则返回空字符串。
力扣:力扣
2.问题分析
这是一道典型的前缀树的问题,但是这一题有一些特殊的要求,返回的答案是:
1.最长的单词 2.这个单词由其他单词逐步构成 3.长度相同返回字典序小的
因此我们需要对前缀树的相关代码进行修改,把字符串一一插入的代码还是不改变的,主要修改的是查找的代码,应该在 trie.next.get(c) == null在增加一个判断为false的条件,就是每一个结点都应该有一个标志true,表示每个节点都存在一个单词,最终一步步构成最长的单词(叶子结点的单词)
3.代码实现
class Solution {public String longestWord(String[] words) {Trie trie = new Trie();for (String word : words) {trie.insert(word);}String longest = "";for (String word : words) {if (trie.search(word)) {if (word.length() > longest.length() || ((word.length() == longest.length()) && (word.compareTo(longest) < 0))) {longest = word;}}}return longest;}
}
class Trie {Map<Character, Trie> next;boolean isEnd;public Trie() {this.next = new HashMap<>();this.isEnd = false;}public void insert(String word) {Trie trie = this;//获得根结点for (char c : word.toCharArray()) {if (trie.next.get(c) == null) {//当前结点不存在trie.next.put(c, new Trie());//创建当前结点}trie = trie.next.get(c);//得到字符c的结点,继续向下遍历}trie.isEnd = true;}public boolean search(String word) {Trie trie = this;//获得根结点for (char c : word.toCharArray()) {if (trie.next.get(c) == null || !trie.next.get(c).isEnd) {//当前结点不存在return false;}trie = trie.next.get(c);//得到字符c的结点,继续向下遍历}return trie.isEnd;}}
相关文章:
前缀树(字典树/Trie) -----Java实现
目录 一.前缀树 1.什么是前缀树 2.前缀树的举例 二.前缀树的实现 1.前缀树的数据结构 1.插入字符串 2.查找字符串 3.查找前缀 三.词典中最长的单词 1.题目描述 2.问题分析 3.代码实现 一.前缀树 1.什么是前缀树 字典树(Trie树)是一种树形…...
申请专利需要具备什么条件
申请专利需要具备什么条件 在我国,如果创造出来了新的发明都可以申请专利权,一旦申请成功之后,自己的发明就受到了法律的保护,任何人不得以违法的手段进行侵犯。那么申请专利需要具备什么条件?今天律赢时代网就为大家…...
【C++】一篇带你搞懂C++“引用”
前言在C语言的学习中,并没有引用这个概念,但是在C中,加入了引用这个概念,说明引用也是很重要的,但是我们怎么理解引用呢?我是这么理解的,例如在水浒传中,108个英雄好汉都是自己的外号…...
蓝桥杯刷题冲刺 | 倒计时19天
作者:指针不指南吗 专栏:蓝桥杯倒计时冲刺 🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾 文章目录1.抓住那头牛2.排列序数1.抓住那头牛 题目 链接: 抓住那头牛 - C语言网 (dotcpp.com…...
Java每日一练(20230321)
目录 1. 出现次数最多的字符 🌟 2. 最后一个单词的长度 🌟 3. 两数之和 🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 出现次数最多的字符并…...
【三维几何学习】从零开始网格上的深度学习-3:Transformer篇(Pytorch)
本文参加新星计划人工智能(Pytorch)赛道:https://bbs.csdn.net/topics/613989052 从零开始网格上的深度学习-3:Transformer篇引言一、概述二、核心代码2.1 位置编码2.2 网络框架三、基于Transformer的网格分类3.1 分类结果3.2 全部代码引言 本文主要内容如下&#…...
一、基础算法3:二分 模板题+算法模板(数的范围,数的三次方根)
文章目录算法模板整数二分算法模板浮点数二分算法模板模板题数的范围原题链接题目题解数的三次方根原题链接题目题解算法模板 整数二分算法模板 bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid 1, r]时使用: int b…...
Spring 源码解析 - Bean创建过程 以及 解决循环依赖
一、Spring Bean创建过程以及循环依赖 上篇文章对 Spring Bean资源的加载注册过程进行了源码梳理和解析,我们可以得到结论,资源文件中的 bean 定义信息,被组装成了 BeanDefinition 存放进了 beanDefinitionMap 容器中,那 Bean 是…...
移除元素(双指针)
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的…...
76.qt qml-QianWindow开源炫酷界面框架(支持白色暗黑渐变自定义控件均以适配)
界面介绍界面支持: 透明 白色 黑色 渐变 单色 静态图 动态图侧边栏支持:抽屉、带折叠、多模式场景控件已集成: 暗黑风格 高亮风格、并附带个人自定义控件及开源demo白色场景如下所示:单色暗黑风格如下所示:用户自定义皮肤如下所示:皮肤预览如下所示:b站入口:https://www.bilibi…...
Python生日蛋糕
目录 前言 底盘 蛋糕 蜡烛 祝福 前言 Hello,小伙伴们晚上好吖!前两天博主满20岁啦(要开始奔三辽呜呜呜),这几天收到了不少小伙伴们的祝福,浪漫的小博主想送给大家一份不一样的生日蛋糕,…...
QT 如何提高 Qt Creator 的编译速度
如何提高编译速度,貌似是一个老生常谈的话题。对于Qter而言,如何提高QT Creator 的编辑速度是一直都是大家所期盼的。本文也是查阅了各路大神的方法后整理出来的,希望对各位有所帮助。 1、在*.pro文件添加预编译机制 QT官方给出的示例&…...
STM32之震动传感器、继电器介绍及实战
目录 一、震动传感器介绍及实战 二、编程代码实现 1、gpio.c---------初始化GPIO口引脚函数 2、调用中断服务函数 3、中断服务函数 4、中断服务回调函数 5、把上述的中断服务回调函数,放入main主函数里 6、结果演示 三、继电器介绍及实战 一、震动传感器介…...
RK3588平台开发系列讲解(显示篇)RK3588 平台 的DP介绍
平台内核版本安卓版本RK3588Linux 5.10Android 12文章目录 一、功能特性二、 DP 输⼊三、DP 输出四、 代码路径沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍 RK3588 平台 DP 的使⽤与调试⽅法。 一、功能特性 RK3588 的 DP ⽀持 1.4a 版本的 DP 协议,最…...
【Java】i++和++i的实现原理
文章目录 i++案例反编译分析扩展 x = x++我们接下来从字节码层面分析: 不了解字节码的可以参考这篇:【精通JVM】字节码指令全解 i++案例 package org.example;public class Main {public static void main...
第十四届蓝桥杯三月真题刷题训练——第 18 天
目录 第 1 题:排列字母 问题描述 运行限制 代码: 第 2 题:GCD_数论 问题描述 输入格式 输出格式 样例输入 样例输出 评测用例规模与约定 运行限制 第 3 题:选数异或 第 4 题:背包与魔法 第 1 题&#x…...
软件测试拿了几个20K offer,分享一波面经
1、你的测试职业发展是什么? 测试经验越多,测试能力越高。所以我的职业发展是需要时间积累的,一步步向着高级测试工程师奔去。而且我也有初步的职业规划,前3年积累测试经验,按如何做好测试工程师的要点去要求自己,不断…...
spring2
1.Spring配置数据源1.1 数据源(连接池)的作用 数据源(连接池)是提高程序性能如出现的事先实例化数据源,初始化部分连接资源使用连接资源时从数据源中获取使用完毕后将连接资源归还给数据源常见的数据源(连接池):DBCP、C3P0、BoneC…...
【Linux】网络编程套接字(中)
🎇Linux: 博客主页:一起去看日落吗分享博主的在Linux中学习到的知识和遇到的问题博主的能力有限,出现错误希望大家不吝赐教分享给大家一句我很喜欢的话: 看似不起波澜的日复一日,一定会在某一天让你看见坚持…...
手撕数据结构—队列
队列队列的话只允许在一端插入,在另外一端删除。插入数据的那一段叫做队尾,出数据的那一段叫做队头(从尾巴插入)。因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的,因为栈的话就是说如…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
Pydantic + Function Calling的结合
1、Pydantic Pydantic 是一个 Python 库,用于数据验证和设置管理,通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发(如 FastAPI)、配置管理和数据解析,核心功能包括: 数据验证:通过…...
