Java Trie の独自のバージョンを作成して作成するために必要な知識を得ようとしていますが、このプロジェクトには困惑しています。ここには非常に基本的な壊れたトライがあります。
Trie に 3 つの単語を追加しています (単語の最初の文字をキーとして使用し、値を追加の TrieNodes として使用します)。お気付きかもしれませんが、プログラムの実行中に isWord の値をチェックするために、TrieNode クラス内に print ステートメントがあります。単語の最後の文字の isWord 変数を True に設定します。したがって、単語の終わりを識別します (後で単語全体を取得するために使用します)。
最初に 3 つの単語を入力すると、出力はすべての単語のすべての文字を出力し、それらが 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