首页 文章

基于阵列的Trie实现 . 子数组中的非null值

提问于
浏览 次
0

我试图从http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/了解Trie的基于数组的实现（参见Java解决方案2 - 使用数组提高性能） .

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分支是否曾被执行过 . 我错过了什么？

Update 1

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

java data-structures trie

2 回答

  • 2

    第一次调用此函数时，else分支确实不会执行 . 但是，随着Trie的填充， p.arr[index] 很可能不为空 .

    例如，调用 insert("i") 将导致在 root.arr['i' - 'a'] 添加新的TrieNode . 第二次调用该函数（例如使用 insert("it") ）将导致检查 p.arr[index] == null 返回false，因为第一个插入已经在根节点处为 i 添加了 TrieNode .

    您可以使用以下main函数对此进行测试（并在 else 分支中放置断点或println语句）

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

    这在我看来非常像一个bug . 如果c-'a'> 26则p.arr [index]不会为null，但会引发ArrayIndexOutOfBounds异常 .

    回复于

相关问题