基於陣列的Trie實現。子數組中的非空值

我試圖從http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/瞭解Trie的基於陣列的實現（請參閱Java解決方案2 - 使用數組提高性能）。基於陣列的Trie實現。子數組中的非空值

public void insert(String word) { 
    TrieNode p = root; 
    for(int i = 0; i < word.length(); i++) { 
     char c = word.charAt(i); 
     int index = c - 'a'; 
     if(p.arr[index] == null) { 
      TrieNode temp = new TrieNode(); 
      p.arr[index] = temp; 
      p = temp; 
     } else { 
      p = p.arr[index]; 
     } 
    } 
    p.isEnd = true; 
}

我不確定else分支是否被執行過。我錯過了什麼？

更新1

給定的字只包含小寫英文字母

來源

2016-12-06 Maksim Dmitriev

邊評論：'INT指數= C-'A';'是完全錯誤的。對於大寫字母，數字，空格和許多標點字符，這會產生一個負數。 –

@Jim，請參閱update 1 –

'TrieNode'的源代碼在哪裏？ –

您第一次調用此函數時，else分支確實不會執行。但是，隨着Trie人數的增加，p.arr[index]很可能不爲空。

例如，調用insert("i")將導致添加一個新的TrieNode在root.arr['i' - 'a']。第二次調用函數（例如insert("it")）將導致檢查p.arr[index] == null返回錯誤，因爲第一個插入已經在根節點處爲i添加了TrieNode。

您可以通過以下主要功能測試這一點（和投入的else分支斷點或println語句，）

public static void main (String[] args) 
{ 
    Trie t = new Trie(); 
    t.insert("i"); 
    t.insert("it"); 
}

來源

2016-12-06 21:23:08 DPenner1

這看起來對我非常喜歡的一個錯誤。如果c'a'> 26，則p.arr [index]不會爲空，但會引發ArrayIndexOutOfBounds異常。

來源

2016-12-06 19:43:11

請參閱更新1 –

基於陣列的Trie實現。子數組中的非空值

回答

相關問題