使用Java Trie时,无法识别词尾。在递归中失败
我正试图创建我自己的JavaTrie版本,以便拥有它,并获得制作它所需的知识,但这个项目让我感到困惑。我这里有一个非常基本的坏球
我在Trie中添加了3个单词(使用单词的第一个字符作为键,值是额外的三元组)。如果您注意到了,我在trinode类中有print语句,用于在程序运行时检查isWord的值。我希望单词中的最后一个字符将isWord变量设置为True。从而识别一个单词的结尾(稍后我将使用它来获取整个单词)
当我第一次输入这三个单词时,输出会打印每个单词进入Trie时的每个字母,并正确识别哪些字符是单词的结尾
但是,如果在输入单词后立即遍历Trie并重新打印Trie中的所有字符及其isWord状态,“Hello”中的“e”现在突然被标识为单词结尾
我已经滔滔不绝地讲了好几个小时,但我不明白为什么会发生这种情况。以下是工作代码:
package testcode;
import java.util.*;
public class TestCode {
public static Trie t;
public static void main (String[] args){
t = new Trie();
t.addWord("hello");
t.addWord("hi");
t.addWord("soup");
//at this point the output correctly identifies word endings.
t.findWords();
/* but when iterating through the hash map it becomes evident that
* when entering the word 'hi' the 'e' in 'hello' had its isWord variable
* changed to true. I followed the logic and I do not see how or why this
* is happening.
*/
}
}
//This Trie class handles the root trie, and Trie commands.
class Trie{
private TrieNode root;
public Trie(){
root = new TrieNode();
}
public void addWord(String word){
root.addWord(word.toLowerCase());
}
public void findWords(){
root.findWords();
}
}
//Trie Node handles the nodes and words within the trie
class TrieNode{
private TrieNode parent;
private boolean isWord;
private boolean hasChildren;
private char character;
private Map<Character, TrieNode> children = new HashMap<>();
public TrieNode(){
hasChildren = false;
isWord = false;
}
public TrieNode(String word){
this();
addWord(word);
}
public void addWord(String word){
char firstChar = word.charAt(0);
if (children.get(firstChar) == null){
if(word.length() > 1){
hasChildren = true;
children.put(firstChar, new TrieNode(word.substring(1)));
children.get(firstChar).parent = this;
System.out.print(firstChar + "--");
System.out.println(isWord);
}
else{
children.put(firstChar, new TrieNode());
if(character == 'e'){
System.out.println("shits about to go down");
}
isWord = true;
System.out.print(firstChar + "--");
System.out.println(isWord);
}
children.get(firstChar).character = firstChar;
}
else {
children.get(firstChar).addWord(word.substring(1));
}
}
public void findWords(){
for(Character key : children.keySet()){
children.get(key).findWords();
System.out.println(children.get(key).character + " -- " + isWord);
}
}
}
此代码生成以下输出:
o--true
l--false
l--false
e--false
h--false
i--true
p--true
u--false
o--false
s--false
p -- true
u -- false
o -- false
s -- false
o -- true
l -- false
l -- false
e -- true //notice the e here is now suddenly a word ending with isWord = true
i -- true
h -- false
# 1 楼答案
有一系列可能的问题。。父/子混淆,在父节点处理叶子案例,包括在建筑和;打印输出等
我注意到,在旧的“findWords”代码中,您打印的是子字符,但父“isWord”标志。构建trie时,“存在子节点”和“创建子节点路径”之间存在不必要的差异,因此“isWord”只能标记在新路径上,而不能标记在现有路径上。构建trie似乎也会在父节点而不是叶节点上设置“isWord”
一般来说,如果案例很可能不可靠,那么代码就是嵌套的意大利面条。在可能的情况下,代码应该是通用的,将其保留在方法的主流程中,除非它真的属于IF
这是clean&;正确代码: