从 Trie 中获取单词列表
我希望使用以下代码来不检查 Trie 中是否有匹配的单词,而是返回以用户输入的前缀开头的所有单词的列表。有人能指出我正确的方向吗?我根本无法让它工作......
public boolean search(String s)
{
Node current = root;
System.out.println("\nSearching for string: "+s);
while(current != null)
{
for(int i=0;i<s.length();i++)
{
if(current.child[(int)(s.charAt(i)-'a')] == null)
{
System.out.println("Cannot find string: "+s);
return false;
}
else
{
current = current.child[(int)(s.charAt(i)-'a')];
System.out.println("Found character: "+ current.content);
}
}
// If we are here, the string exists.
// But to ensure unwanted substrings are not found:
if (current.marker == true)
{
System.out.println("Found string: "+s);
return true;
}
else
{
System.out.println("Cannot find string: "+s +"(only present as a substring)");
return false;
}
}
return false;
}
}
I'm looking to use the following code to not check whether there is a word matching in the Trie but to return a list all words beginning with the prefix inputted by the user. Can someone point me in the right direction? I can't get it working at all.....
public boolean search(String s)
{
Node current = root;
System.out.println("\nSearching for string: "+s);
while(current != null)
{
for(int i=0;i<s.length();i++)
{
if(current.child[(int)(s.charAt(i)-'a')] == null)
{
System.out.println("Cannot find string: "+s);
return false;
}
else
{
current = current.child[(int)(s.charAt(i)-'a')];
System.out.println("Found character: "+ current.content);
}
}
// If we are here, the string exists.
// But to ensure unwanted substrings are not found:
if (current.marker == true)
{
System.out.println("Found string: "+s);
return true;
}
else
{
System.out.println("Cannot find string: "+s +"(only present as a substring)");
return false;
}
}
return false;
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(10)
我在尝试制作文本自动完成模块时遇到了这个问题。我通过创建一个 Trie 树来解决这个问题,其中每个节点都包含它的父节点以及子节点。首先,我搜索从输入前缀开始的节点。然后我在 Trie 上应用了遍历,以它的根作为前缀节点来探索子树的所有节点。每当遇到叶节点时,就意味着找到了从输入前缀开始的单词的结尾。从该叶节点开始,我迭代父节点,获取父节点的父节点,并到达子树的根。在这样做的同时,我不断在堆栈中添加节点的键。最后,我获取了前缀并开始通过弹出堆栈来附加它。我继续将单词保存在 ArrayList 中。在遍历结束时,我得到从输入前缀开始的所有单词。这是带有用法示例的代码:
-
示例
I faced this problem while trying to make a text auto-complete module. I solved the problem by making a Trie in which each node contains it's parent node as well as children. First I searched for the node starting at the input prefix. Then I applied a Traversal on the Trie that explores all the nodes of the sub-tree with it's root as the prefix node. whenever a leaf node is encountered, it means that the end of a word starting from input prefix has been found. Starting from that leaf node I iterate through the parent nodes getting parent of parent, and reach the root of the subtree. While doing so I kept adding the keys of nodes in a stack. In the end I took the prefix and started appended it by popping the stack. I kept on saving the words in an ArrayList. At the end of the traversal I get all the words starting from the input prefix. Here is the code with usage example:
-
Example
构建 Trie 后,您可以从找到前缀的节点开始进行 DFS:
After building Trie, you could do DFS starting from node, where you found prefix:
最简单的解决方案是使用深度优先搜索。
您沿着字典树查找,逐个字母地匹配输入。然后,一旦没有更多的字母可匹配,该节点下的所有内容都是您想要的字符串。递归地探索整个子树,在深入到其节点时构建字符串。
The simplest solution is to use a depth-first search.
You go down the trie, matching letter by letter from the input. Then, once you have no more letter to match, everything under that node are strings that you want. Recursively explore that whole subtrie, building the string as you go down to its nodes.
在我看来,这更容易递归解决。它会像这样:
Print
,打印以您作为参数给出的节点为根的 trie 中的所有节点。 Wiki 告诉您如何执行此操作(查看排序)。Print
函数。然后只需确保在每个单词之前输出前缀,因为这将为您提供没有前缀的所有单词。如果你不太关心效率,你可以只在主根节点上运行
Print
并只打印那些以你感兴趣的前缀开头的单词。这更容易实现,但速度较慢。This is easier to solve recursively in my opinion. It would go something like this:
Print
that prints all the nodes in the trie rooted in the node you give as parameter. Wiki tells you how to do this (look at sorting).Print
function with this node as the parameter. Then just make sure you also output the prefix before each word, since this will give you all the words without their prefix.If you don't really care about efficiency, you can just run
Print
with the main root node and only print those words that start with the prefix you're interested in. This is easier to implement but slower.您需要从找到前缀的节点开始遍历子树。
以同样的方式开始,即找到正确的节点。然后,不检查其标记,而是遍历该树(即遍历其所有后代;DFS< /a> 是一个很好的方法),保存用于从第一个节点到达“当前”节点的子字符串。
如果当前节点被标记为单词,则输出* 到达的前缀+子串。
* 或将其添加到列表或其他内容中。
You need to traverse the sub-tree starting at the node you found for the prefix.
Start in the same way, i.e. finding the correct node. Then, instead of checking its marker, traverse that tree (i.e. go over all its descendants; a DFS is a good way to do it) , saving the substring used to reach the "current" node from the first node.
If the current node is marked as a word, output* the prefix + substring reached.
* or add it to a list or something.
我为 ITA 谜题之一构建了一次特里树
}
I built a trie once for one of ITA puzzles
}
您需要使用列表
列表<字符串> myList = new ArrayList();
if(找到匹配的字符串)
myList.add(stringToAdd);
You would need to use a List
List<String> myList = new ArrayList<String>();
if(matchingStringFound)
myList.add(stringToAdd);
在 for 循环之后,添加对 printAllStringsInTrie(current, s); 的调用
After your for loop, add a call to printAllStringsInTrie(current, s);
当您的 TrieNode 如下所示时,可以使用以下递归代码:
这段代码工作正常。
The below recursive code can be used where your TrieNode is like this:
This code works fine.
简单的递归 DFS 算法可用于查找给定前缀的所有单词。
示例 Trie 节点:
查找给定前缀的所有单词的方法:
完整代码可以在下面找到:
TrieDataStructure 示例
Simple recursive DFS algorithm can be used to find all words for a given prefix.
Sample Trie Node:
Method to find all words for a given prefix:
Complete code can be found at below:
TrieDataStructure Example