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

前缀树(字典树/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.什么是前缀树 字典树&#xff08;Trie树&#xff09;是一种树形…...

​申请专利需要具备什么条件

​申请专利需要具备什么条件 在我国&#xff0c;如果创造出来了新的发明都可以申请专利权&#xff0c;一旦申请成功之后&#xff0c;自己的发明就受到了法律的保护&#xff0c;任何人不得以违法的手段进行侵犯。那么申请专利需要具备什么条件&#xff1f;今天律赢时代网就为大家…...

【C++】一篇带你搞懂C++“引用”

前言在C语言的学习中&#xff0c;并没有引用这个概念&#xff0c;但是在C中&#xff0c;加入了引用这个概念&#xff0c;说明引用也是很重要的&#xff0c;但是我们怎么理解引用呢&#xff1f;我是这么理解的&#xff0c;例如在水浒传中&#xff0c;108个英雄好汉都是自己的外号…...

蓝桥杯刷题冲刺 | 倒计时19天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.抓住那头牛2.排列序数1.抓住那头牛 题目 链接&#xff1a; 抓住那头牛 - C语言网 (dotcpp.com…...

Java每日一练(20230321)

目录 1. 出现次数最多的字符 &#x1f31f; 2. 最后一个单词的长度 &#x1f31f; 3. 两数之和 &#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 出现次数最多的字符并…...

【三维几何学习】从零开始网格上的深度学习-3:Transformer篇(Pytorch)

本文参加新星计划人工智能(Pytorch)赛道&#xff1a;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]时使用&#xff1a; int b…...

Spring 源码解析 - Bean创建过程 以及 解决循环依赖

一、Spring Bean创建过程以及循环依赖 上篇文章对 Spring Bean资源的加载注册过程进行了源码梳理和解析&#xff0c;我们可以得到结论&#xff0c;资源文件中的 bean 定义信息&#xff0c;被组装成了 BeanDefinition 存放进了 beanDefinitionMap 容器中&#xff0c;那 Bean 是…...

移除元素(双指针)

给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并原地修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的…...

76.qt qml-QianWindow开源炫酷界面框架(支持白色暗黑渐变自定义控件均以适配)

界面介绍界面支持: 透明 白色 黑色 渐变 单色 静态图 动态图侧边栏支持:抽屉、带折叠、多模式场景控件已集成: 暗黑风格 高亮风格、并附带个人自定义控件及开源demo白色场景如下所示:单色暗黑风格如下所示:用户自定义皮肤如下所示:皮肤预览如下所示:b站入口:https://www.bilibi…...

Python生日蛋糕

目录 前言 底盘 蛋糕 蜡烛 祝福 前言 Hello&#xff0c;小伙伴们晚上好吖&#xff01;前两天博主满20岁啦&#xff08;要开始奔三辽呜呜呜&#xff09;&#xff0c;这几天收到了不少小伙伴们的祝福&#xff0c;浪漫的小博主想送给大家一份不一样的生日蛋糕&#xff0c…...

QT 如何提高 Qt Creator 的编译速度

如何提高编译速度&#xff0c;貌似是一个老生常谈的话题。对于Qter而言&#xff0c;如何提高QT Creator 的编辑速度是一直都是大家所期盼的。本文也是查阅了各路大神的方法后整理出来的&#xff0c;希望对各位有所帮助。 1、在*.pro文件添加预编译机制 QT官方给出的示例&…...

STM32之震动传感器、继电器介绍及实战

目录 一、震动传感器介绍及实战 二、编程代码实现 1、gpio.c---------初始化GPIO口引脚函数 2、调用中断服务函数 3、中断服务函数 4、中断服务回调函数 5、把上述的中断服务回调函数&#xff0c;放入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 题&#xff1a;排列字母 问题描述 运行限制 代码&#xff1a; 第 2 题&#xff1a;GCD_数论 问题描述 输入格式 输出格式 样例输入 样例输出 评测用例规模与约定 运行限制 第 3 题&#xff1a;选数异或 第 4 题&#xff1a;背包与魔法 第 1 题&#x…...

软件测试拿了几个20K offer,分享一波面经

1、你的测试职业发展是什么? 测试经验越多&#xff0c;测试能力越高。所以我的职业发展是需要时间积累的&#xff0c;一步步向着高级测试工程师奔去。而且我也有初步的职业规划&#xff0c;前3年积累测试经验&#xff0c;按如何做好测试工程师的要点去要求自己&#xff0c;不断…...

spring2

1.Spring配置数据源1.1 数据源&#xff08;连接池&#xff09;的作用 数据源(连接池)是提高程序性能如出现的事先实例化数据源&#xff0c;初始化部分连接资源使用连接资源时从数据源中获取使用完毕后将连接资源归还给数据源常见的数据源(连接池)&#xff1a;DBCP、C3P0、BoneC…...

【Linux】网络编程套接字(中)

&#x1f387;Linux&#xff1a; 博客主页&#xff1a;一起去看日落吗分享博主的在Linux中学习到的知识和遇到的问题博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a; 看似不起波澜的日复一日&#xff0c;一定会在某一天让你看见坚持…...

手撕数据结构—队列

队列队列的话只允许在一端插入&#xff0c;在另外一端删除。插入数据的那一段叫做队尾&#xff0c;出数据的那一段叫做队头&#xff08;从尾巴插入&#xff09;。因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的&#xff0c;因为栈的话就是说如…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...