`
Para_dox
  • 浏览: 10079 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

JAVA字典树的查找

阅读更多
我的第一篇技术类博客,看周围朋友都把每天学习的东西记录在博客上,感觉还是挺好的。
那我也就以此作为一个开始吧。

需求是给定若干个字母,要求查找出这若干个字母组成的最长长度的单词。
字典树已生成。
public static String GenerateLongestWords(TriNode root, String src, String longestWord, int currentDepth, char[] word)
	{
		TriNode node = null;
		StringBuffer buffer = new StringBuffer(src);
		
		List<TriNode> triLink = root.triLink;
		Iterator<TriNode> iterator = triLink.iterator();
		
		while(iterator.hasNext())
		{
			node = iterator.next();
			if(node.ch == '#')
			{
				if(currentDepth > longestWord.length())
				{
					char[] word2 = new char[currentDepth];
					for(int j = 0 ; j< currentDepth ; j++)
						word2[j] = word[j];
					longestWord = String.copyValueOf(word2);
				}
			}
			else
			{
				//check whether we have a char available
				int i = src.indexOf(node.ch);
				if(i >= 0)
				{		
					word[currentDepth] = node.ch;
					//reduce the number of this char in our repository
					buffer.deleteCharAt(i);
					//following this path , DFS
					root = node;
					longestWord = GenerateLongestWords(root, buffer.toString(), longestWord, currentDepth+1, word);  
					buffer = new StringBuffer(src);
				}
				else 
				{
					//do nothing
				}
			}
		}
		return longestWord;
	}

src是可用的字母组成的字符串,longestWord最初的传入值为空
分享到:
评论

相关推荐

    字典树~java语言

    下面是一个简化的Java字典树节点类示例: ```java public class TrieNode { private boolean isEndOfWord; private TrieNode[] children; public TrieNode() { this.isEndOfWord = false; this.children = ...

    Java实现字典树TrieTree

    下面将详细介绍Java如何实现字典树以及其在实际应用中的价值。 1. **字典树的基本结构** 字典树是一种树形数据结构,每个节点包含一个字符,并且指向若干个子节点,代表该字符后可能接续的下一个字符。根节点不...

    字典树实例--java实现

    这个实例是用Java语言实现的,我们将深入探讨字典树的工作原理和Java实现的关键点。 首先,字典树的核心概念是利用节点来存储字符串的字符,每个节点可能有多个子节点,对应于下一个可能的字符。根节点通常不包含...

    快速单词拼写检错程序(字典树实现)

    这个Java程序利用了数据结构——字典树(Trie),也被称为前缀树或PAT树,它在处理字符串相关的搜索问题时表现出色。下面我们将深入探讨字典树的工作原理及其在拼写检错中的应用。 字典树是一种树形数据结构,每个...

    可变长数组和字典树

    在Java中,Trie.java文件很可能包含了一个字典树的实现,包含了基本的插入、查找和遍历等方法。 字典树在实际应用中非常常见,如搜索引擎的关键词索引、拼写检查、IP路由表、电话号码簿等。通过Trie,可以快速查找...

    字典树_字典树_

    在计算机科学中,字典树常被用于实现自动补全、关键词搜索、IP路由等功能,因为它能快速查找以特定前缀开头的所有字符串。下面将详细介绍字典树的基本概念、结构以及如何使用它。 字典树的构造: 1. 每个节点代表一...

    Trie树(字典树)的介绍及Java实现

    Trie树,也被称为字典树或前缀树,是一种数据结构,主要用于高效地存储和检索字符串集合中的数据。在Trie树中,每个节点代表一个字符串的前缀,从根节点到某个节点的路径上的字符序列构成了该节点对应的字符串。这种...

    深度优先遍历字典树(统计单词出现的个数)

    字典树是一种数据结构,常用于存储大量字符串,它允许我们快速查找以特定前缀开头的所有单词。 在Java中,实现字典树通常涉及以下步骤: 1. **定义节点类**:创建一个表示字典树节点的类,包含一个字符字段(代表...

    java实现字典

    - **数据结构**:为了高效地存储和访问词汇信息,可能需要设计合适的数据结构,如哈希表(HashMap)用于快速查找,或者Trie树(字典树)用于高效的前缀搜索。 - **异步处理**:考虑到查词、改错和联想可能涉及较重...

    使用字典树和Hashtable两种方法解POJ 2503(JAVA)

    字典树,又称Trie或前缀树,是一种用于快速查找和插入字符串的数据结构。在字典树中,每个节点代表一个字符串的前缀,根节点代表空字符串。通过沿着节点路径向下遍历,我们可以高效地查询某个字符串是否存在,或者...

    字典树练习 POJ 1056

    但通常,字典树的应用包括单词查找、自动补全、IP地址路由等。在解决此类问题时,我们需要考虑以下几点: 1. **字典树的基本构造**:理解字典树的节点结构,每个节点包含一个字符和指向子节点的指针数组。根节点不...

    双数组字典树的-java实现,用于敏感词过滤

    双数组字典树(Double Array Trie,简称DAT)是一种高效的数据结构,主要用于字符串搜索和匹配,尤其在处理大量敏感词过滤的场景下表现突出。它是由日本科学家原望治(Hideo Hiraoka)提出的,相比传统的Trie树,DAT...

    dic.rar_dictionary java_java 翻译_java翻译程序_字典 java_英汉字典

    从标签“dictionary_java”,我们可以推断出这个程序可能包括了一些数据结构,如字典树(Trie树)或哈希表,用于高效地存储和查找单词。"java_翻译"和"java翻译程序"暗示了这个程序可能使用了Java的字符串操作和可能...

    大一下学期期末作业(字典树优化)_管理系统_学校管理系统_

    2. 编程语言:选择合适的编程语言,如Python、Java或C++,来实现字典树的数据结构和相关的查询接口。 3. 数据库连接:可能需要与数据库进行交互,以便将字典树与实际数据存储相结合。 4. 用户界面:设计友好的用户...

    ac自动机java版

    在Java中实现AC自动机,通常需要设计一个TrieNode类来表示字典树的节点,包含字符、子节点、失败指针等属性,并提供插入模式、构建失败函数和在线匹配的方法。"ahocorasick_java-1.1"这个文件可能是实现AC自动机的...

    用java实现得各种查找

    4. **二叉搜索树查找**: 二叉搜索树(BST)是一种特殊的二叉树,其中每个节点的左子树只包含比其小的元素,右子树只包含比其大的元素。查找操作在BST中自顶向下进行,时间复杂度取决于树的形状,理想情况下为O(log ...

    基于Trie树模仿谷歌百度搜索框提示

    首先,我们要理解什么是Trie树,也被称为前缀树或字典树。Trie树是一种特殊的树形数据结构,用于存储一个字符串集合。它的特点是每个节点代表一个字符串的前缀,根节点不包含任何字符,而叶节点则表示完整的单词。...

    快速单词拼写程序(JAVA源码)

    程序运用了字典树(Trie树)这一数据结构,来实现高效、快速的单词匹配与查找。接下来,我们将详细讨论这个程序涉及到的关键知识点。 首先,**字典树**是一种非常有效的字符串检索数据结构。它将所有可能的单词前缀...

    Java实现字典功能xxxxxx

    在Java编程语言中,实现字典...总之,实现Java字典功能涉及选择合适的数据结构(如`HashMap`或`TreeMap`)、应用有效的搜索算法,以及可能的GUI设计。通过熟练掌握这些知识点,开发者可以构建出高效、易用的字典应用。

    这是针对大数据集优化了的双数组字典树,使得在大数据集上构建速度也比较满意,查询速度不随数据集的增加而增加,同时解决了.zip

    1. **源代码**:优化的双数组字典树实现,包括C++、Java或其他编程语言的实现。 2. **文档**:详细描述了优化方法和使用指南,帮助用户理解和应用此数据结构。 3. **测试数据和脚本**:用于验证和评估优化效果的示例...

Global site tag (gtag.js) - Google Analytics