基于阵列的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

给定的字只包含小写英文字母

边评论：'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"); 
}

答

这看起来对我非常喜欢的一个错误。如果c'a'> 26，则p.arr [index]不会为空，但会引发ArrayIndexOutOfBounds异常。

请参阅更新1 –

基于阵列的Trie实现。子数组中的非空值

相关推荐