字典树(Trie)的java实现
JAVA 实现 字典 Trie
2023-09-11 14:20:30 时间
一、定义
字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
![](https://images2015.cnblogs.com/blog/689103/201510/689103-20151017165124335-192380633.jpg)
字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
二、java代码实现
//字典树的java实现 public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); root.wordEnd = false; } public void insert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { Character c = new Character(word.charAt(i)); if (!node.childdren.containsKey(c)) { node.childdren.put(c, new TrieNode()); } node = node.childdren.get(c); } node.wordEnd = true; } public boolean search(String word) { TrieNode node = root; boolean found = true; for (int i = 0; i < word.length(); i++) { Character c = new Character(word.charAt(i)); if (!node.childdren.containsKey(c)) { return false; } node = node.childdren.get(c); } return found && node.wordEnd; } public boolean startsWith(String prefix) { TrieNode node = root; boolean found = true; for (int i = 0; i < prefix.length(); i++) { Character c = new Character(prefix.charAt(i)); if (!node.childdren.containsKey(c)) { return false; } node = node.childdren.get(c); } return found; } } public class TrieNode { Map<Character, TrieNode> childdren; boolean wordEnd; public TrieNode() { childdren = new HashMap<Character, TrieNode>(); wordEnd = false; } }
相关文章
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 677 键值映射(字典树)
- Java实现 LeetCode 676 实现一个魔法字典(暴力)
- Java实现 LeetCode 524 通过删除字母匹配到字典里最长单词(又是一道语文题)
- Java实现 LeetCode 524 通过删除字母匹配到字典里最长单词(又是一道语文题)
- Java实现 LeetCode 386 字典序排数
- Java实现 LeetCode 337 打家劫舍 III(三)
- Java 实现 蓝桥杯 生兔子问题
- java实现第三届蓝桥杯数量周期
- java实现第五届蓝桥杯排列序数
- Java实现第九届蓝桥杯小朋友崇拜圈
- Java实现 蓝桥杯 历届试题 危险系数
- java实现漏掉的账目明细
- Java实现字符串转换成整数
- Java实现 蓝桥杯VIP 算法提高 打水问题
- Java实现 蓝桥杯 历届试题 核桃的数量
- Java实现蓝桥杯 算法提高 身份证号码升级
- Java实现蓝桥杯 算法提高 身份证号码升级
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Trie树(字典树)的介绍及Java实现
- 使用Java标准的java.util.EventListener实现观察者-发布者设计模式
- Atitit java播放器调音速率快慢的实现 目录 1.1. 原理 本质上是改变采样率即可1 2. 使用Java增加/降低AudioInputStream的音频播放速度(Increase/dec
- JAVA多线程实现的三种方式
- java-信息安全(十二)-数字证书、CA证书【Java证书体系实现】