前缀树(字典树/Trie) -----Java实现
创始人
2025-05-31 18:32:40
0

一.前缀树

1.什么是前缀树

字典树(Trie树)是一种树形数据结构,常用于字符串的存储和查找。字典树的核心思想是利用字符串之间的公共前缀来节省存储空间和提高查询效率。它是一棵多叉树,每个节点代表一个字符串的前缀,从根节点到叶子节点的路径组成一个字符串

字典树的根节点不包含字符,每个子节点代表一个字符,从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串,通常使用一个标志来标记一个节点代表的字符串是否存在。当需要在一组字符串中查找某个字符串时,可以利用字典树来实现高效的查找操作。

2.前缀树的举例

例如对字符串数组{"goog","google","bai","baidu","a"}建立前缀树,此时我们可以很清晰的看到前缀树的一些特征:

  • 根结点不保存字符
  • 前缀树是一颗多叉树
  • 前缀树的每个节点保存一个字符
  • 具有相同前缀的字符串保存在同一条路径上
  • 字符串的尾处相应的在前缀树上也有结束的标志

二.前缀树的实现 

 力扣上的208题就是实现前缀树:力扣

1.前缀树的数据结构

在写代码的时候,我偏向于用哈希表来存储结点的信息,有的也可以用数组来存储结点的信息,本质上都是一样的

public class Trie {Map 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 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;}}

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作: 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统(六):学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤: 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器(LPUART) 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式,否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日,Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组,我们想大量频繁的去访问L到R这个区间的和,...
windows安装JDK步骤 一、 下载JDK安装包 下载地址:https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1,关于nodejs2,配置环境变量3,总结 前言...
Linux学习之端口、网络协议... 端口:设备与外界通讯交流的出口 网络协议:   网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累: GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...