Implementierung eines Trie in Java

Question

Ich habe die Trie-Datenstruktur in Java implementiert, bekomme aber nicht die richtige Antwort, wenn ich den Code ausführe. Ich habe den Trie mit einigen einfachen Strings gebaut. Ich suche dann nach Wörtern und Präfixen, aber das Ergebnis ist nicht korrekt. Ich habe versucht, es viel zu debuggen, aber immer noch nicht finden, wo es falsch sein könnte.

Trie.java:

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

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")); 
    } 
} 

ich die Topcoder Trie tutorial bezeichnet, dies umzusetzen.

Answer 1

Die else-Klausel in der addWord Methode ist definitiv falsch (es könnten auch andere Fehler, sein):

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

Ihr Code erzeugt immer einen neuen Stützpunkt. Das ist falsch. Sie sollten es tun, wenn und nur wenn es für den gegebenen Charakter noch keine Kante gibt. Das heißt, es sollte wie folgt aussehen:

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

Es gibt ein paar andere Probleme mit Ihrer Implementierung. Zum Beispiel arbeitet die String.substring Methode in linearer Zeit, so dass das Hinzufügen eines Strings zu einem Trie quadratische Zeit erfordert. Sie können das beheben, indem Sie über alle Zeichen des Wortes iterieren, anstatt für seine Teilzeichenfolgen eine Rekursion zu erstellen. Beseitigung Rekursion ist auch eine gute Idee, weil Sie für längere Strings in Stack-Overflow-Fehler ausführen können.