在Java中實現Trie

我在Java中實現了Trie數據結構，但在運行代碼時沒有得到正確的答案。我使用一些簡單的字符串構建了trie。然後我搜索單詞和前綴，但結果不正確。我試過很多次，但仍然找不到可能出錯的地方。在Java中實現Trie

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

我提到的Topcoder Trie tutorial來實現這一點。

來源

2017-04-19 ayushgp

我開始測試1字符的字符串，然後是2個字符的字符串，並檢查trie的完整狀態。 – 9000

使用調試器逐步完成，並仔細觀察邊緣情況。尤其要注意當你創建一個新的頂點時，你需要在創建第一個頂點之後重用它們。 –

在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方法在線性時間內工作，因此向樹中添加字符串需要二次時間。您可以通過迭代單詞的所有字符來修復該問題，而不是對其子字符串進行遞歸。消除遞歸也是一個好主意，因爲對於較長的字符串可能會遇到堆棧溢出錯誤。

來源

2017-04-19 20:38:51 kraskevich

在Java中實現Trie

回答

相關問題