Java에서 Trie 구현

Question

Java에서 Trie 데이터 구조를 구현했지만 코드를 실행할 때 정답을 얻지 못하고 있습니다. 나는 간단한 문자열을 사용하여 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.

Answer 1

addWord 방법에 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 차 시간이 필요합니다. 그 부분 문자열을 재귀 적으로 만드는 대신 단어의 모든 문자를 반복하여 수정할 수 있습니다. 더 긴 문자열에 대해 스택 오버플로 오류가 발생할 수 있으므로 제거 재귀도 좋습니다.