JavaでTrieを実装する

Question

JavaでTrieデータ構造を実装しましたが、コードを実行しているときに正しい答えが得られません。私は単純な文字列を使ってトライを作りました。私は単語と接頭辞を検索していますが、結果は適切ではありません。私はそれを多くデバッグしようとしましたが、それが間違っているかもしれない場所を見つけることができません。

Trie.java：私はこれを実装するためにTopcoder Trie tutorial呼ば

public class TrieTester { 
    public static void main(String[] args) { 
     Trie trie = new Trie(); 
     trie.addWord("Ayush"); 
     trie.addWord("Ayur"); 
     trie.addWord("Ayub"); 
     trie.addWord("Ayan"); 
     trie.addWord("Bhushan"); 

     // Should output 0, outputs 0 
     System.out.println("Count of word Ayus: " + trie.countWords("Ayus")); 

     // Should output 1, outputs 0 
     System.out.println("Count of word Ayush: " + trie.countWords("Ayush")); 

     // Should output 4, outputs 1 
     System.err.println("Count of prefix Ay: " + trie.countPrefixes("Ay")); 
    } 
} 

public class Trie { 

    public class Vertex { 
     public int words; 
     public int prefixes; 
     public Vertex edges[] = new Vertex[26]; 

     public Vertex() { 
      this.words = 0; 
      this.prefixes = 0; 
     } 
    } 

    private Vertex root; 

    Trie() { 
     this.root = new Vertex(); 
    } 

    private void addWord(Vertex vertex, String word) { 
     if (word.isEmpty()) { 
      vertex.words++; 
     } else { 
      vertex.prefixes++; 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      vertex.edges[indexOfNextChar] = new Vertex(); 
      this.addWord(vertex.edges[indexOfNextChar], word.substring(1)); 
     } 
    } 

    private int countWords(Vertex vertex, String word) { 
     if (!word.isEmpty()) { 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      if (vertex.edges[indexOfNextChar] == null) { 
       return 0; 
      } else { 
       return this.countWords(vertex.edges[indexOfNextChar], word.substring(1)); 
      } 
     } else { 
      return vertex.words; 
     } 
    } 

    private int countPrefixes(Vertex vertex, String word) { 
     if (!word.isEmpty()) { 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      if (vertex.edges[indexOfNextChar] == null) { 
       return 0; 
      } else { 
       return this.countPrefixes(vertex.edges[indexOfNextChar], word.substring(1)); 
      } 
     } else { 
      return vertex.prefixes; 
     } 
    } 

    public void addWord(String word) { 
     this.addWord(this.root, word.toLowerCase()); 
    } 

    public int countPrefixes(String word) { 
     if (word.length() != 0) { 
      return this.countPrefixes(this.root, word.toLowerCase()); 
     } 
     return -1; 
    } 

    public int countWords(String word) { 
     if (word.length() != 0) { 
      return this.countWords(this.root, word.toLowerCase()); 
     } 
     return -1; 
    } 
} 

TrieTester.java。 addWord方法で

Answer 1

else句は（あまりにも、他のバグがあるかもしれない）確かに間違っています：

vertex.prefixes++; 
int indexOfNextChar = (int) word.charAt(0) - 97; 
vertex.edges[indexOfNextChar] = new Vertex(); 
this.addWord(vertex.edges[indexOfNextChar], word.substring(1)); 

あなたのコードは、常に新しい頂点を作成します。それは間違っている。指定された文字のエッジがまだない場合にのみ、それを行う必要があります。つまり、次のようになります。

if (vertex.edges[indexOfNextChar] == null) { 
    vertex.edges[indexOfNextChar] = new Vertex(); 
} 

実装には他にもいくつか問題があります。たとえば、String.substringメソッドは線形時間で動作するため、文字列をトライに追加するには2次の時間が必要です。その部分文字列を再帰的に作成するのではなく、単語のすべての文字を繰り返し処理することで修正できます。 長い文字列に対してスタックオーバーフローエラーが発生する可能性があるため、消去再帰も良い考えです。