Java中关于字典树的算法实现
字典树(前缀树)算法实现
前言
字典树,又称单词查找树,是一个典型的 一对多的字符串匹配算法。“一”指的是一个模式串,“多”指的是多个模板串。字典树经常被用来统计、排序和保存大量的字符串。它利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。
字典树有3个基本性质:
根节点不包含字符,其余的每个节点都包含一个字符;
从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
每个节点的所有子节点包含的字符都不相同。
pass
参数:代表从这个点经过的单词数量。root根即就是整棵树有多少单词。
end
参数: 代表在这个点结束的单词有几个。例如: 上图有两个 hello,在o结点的end参数就是2。
实现的基本功能: 增删查。
算法解析
首先是结点的参数:
public class Node { public int pass; public int end; public Node[] nexts; //下一个字母的地址 public Node() { pass = 0; end = 0; nexts = new Node[26]; //这里我们就以小写字母为例 } }
下面就是基本功能的实现:
import java.util.Scanner; public class Main { public static void main(String[] args) { String[] arr = {"hello", "hello"}; Trie root = new Trie(); for (int i = 0; i < arr.length; i++) { root.addWord(arr[i]); } //root.delWord("hello"); Scanner sc = new Scanner(System.in); String s = sc.nextLine(); if (root.searchWord(s) != 0) { System.out.println("该字典树有这个" + s + " 单词"); } } public static class Node { public int pass; public int end; public Node[] nexts; //下一个字母的地址 public Node() { pass = 0; end = 0; nexts = new Node[26]; } } public static class Trie { private Node root; public Trie() { root = new Node(); } //增加 public void addWord(String str) { char[] arr = str.toCharArray(); root.pass++; Node node = root; for (char s : arr) { int index = s - 'a'; //以相应的ASCII码值差值,进行数组的下标存储 if (node.nexts[index] == null) { node.nexts[index] = new Node(); } node = node.nexts[index]; node.pass++; //经过这个结点,pass就加1 } node.end++; } //删除 public void delWord(String str) { //删除之前,应该查询一下这颗树有没有这个单词 while (searchWord(str) != 0) { char[] arr = str.toCharArray(); Node node = root; node.pass--; for (int i = 0; i < str.length(); i++) { int index = arr[i] - 'a'; node = node.nexts[index]; node.pass--; } node.end--; } } //查找 public int searchWord(String str) { if (str == null) { return 0; } char[] arr = str.toCharArray(); Node node = root; for (int i = 0; i < str.length(); i++) { int index = arr[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; //返回最后那一个结点的end值即可 } } }
到此这篇关于Java中关于字典树的算法实现的文章就介绍到这了,更多相关Java 字典树内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20