Работа с Java Trie не позволяет определить окончания слов. Сбой где-то в рекурсии

Question

Я пытаюсь создать свою собственную версию Java Trie, чтобы получить ее, и получить знания, необходимые для ее создания, но этот проект меня озадачил. У меня здесь очень сложная трещина.

Я добавляю 3 слова в Trie (используя первый символ слова в качестве ключа, а значение - дополнительные TrieNodes). Если вы заметили, у меня есть инструкции print внутри класса TrieNode, чтобы проверить значения isWord по мере запуска программы. Я хочу, чтобы последний символ в слове имел переменную isWord, установленную в True. Таким образом, определение конца слова (которое я позже использую для получения всего слова).

Когда я впервые ввел три слова, вывод печатает каждую букву каждого слова, когда они входят в Trie, и правильно идентифицирует, какие символы являются окончаниями слов.

Однако, если НЕМЕДЛЕННО после ввода слов, я пересекаю Trie и перепечатываю все символы в Trie и их статус isWord, 'e' в "Hello" теперь внезапно идентифицируется как слово, заканчивающееся?

Я наполнил это часами, и я просто не понимаю, почему это происходит. Ниже приведено рабочий код:

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 

Answer 1

Существовал целый ряд возможных вопросов .. Parent/Child путаница, ведение дел Листа в родительском узле, как в строительстве & распечатки и т.д.

Заметаю код своего старый «findWords», вы печатали ребенок характер но родительского флаг «isWord». У здания trie было нежелательное расхождение между «дочерним узлом» и «созданием путей дочерних узлов» - таким, что «isWord» может быть помечен только на новых путях, а не на существующих путях. Построение trie также показалось, что он задал 'isWord' на родительском, а не на листовом узле.

В общем, код, который является спагетти вложенных случаев IF, скорее всего, будет ненадежным. Код должен быть распространен там, где это возможно, - держать его в основном потоке метода, если он не действительно действительно входит в IF.

Вот чистый & правильный код:

class TrieNode{ 
    private TrieNode parent; 
    private boolean isWord; 
    private boolean hasChildren; 
    private char character; 
    private Map<Character, TrieNode> children = new HashMap<>(); 

    public TrieNode(){ 
     this.hasChildren = false; 
     this.isWord = false; 
    } 
    public TrieNode (char ch) { 
     this.character = ch; 
     this.hasChildren = false; 
     this.isWord = false; 
    } 

    public void addWord (String word){ 
     if (word.length() == 0) { 
      this.isWord = true; 
      System.out.println(character + " -- " + isWord); 
      return; 
     } 

     // represent the Child Node; 
     //  -- 
     char firstChar = word.charAt(0); 
     TrieNode child = children.get(firstChar); 
     if (child == null){ 
      child = new TrieNode(firstChar); 
      children.put(firstChar, child); 
      child.parent = this; 
      hasChildren = true; 
     } 

     // add Remaining Word; 
     //  -- call for 1-length words, as 0-length at Child sets 'IsWord'! 
     child.addWord(word.substring(1)); 

     // print building here. 
     System.out.println(character + " -- " + isWord); 
    } 



    public void findWords(){ 
     for(Character key : children.keySet()){ 
      children.get(key).findWords(); 
     } 
     System.out.println(character + " -- " + isWord);  
    } 
}