Java实现Trie字典树插入搜索功能时search返回false问题排查

问题定位 #

你代码的核心错误出在insert方法的节点创建逻辑里：

• 你已经正确计算了当前字符对应数组的下标index = c - 'a'，但创建新节点赋值的时候，错误使用了循环变量i作为数组下标，而不是计算得到的index。
  这就导致插入的节点位置完全错乱，搜索的时候自然找不到对应路径，返回false。

修复方案 #

只需要修改insert方法里新节点赋值的那一行即可：
把原来的

current.children[i] = node;

修改为

current.children[index] = node;

修复后完整可运行代码 #

public class trie {
    
    private class TrieNode{
        TrieNode[] children;
        boolean isWord;
        public TrieNode() {
            this.children = new TrieNode[26];
            this.isWord = false;
            for(int i= 0; i < 26; i++) {
                this.children[i] = null;
            }
        }
    }
    
    TrieNode root;
    
    public trie() {
        root = new TrieNode();
    }
    
    public void insert(String s) {
        if(s == null || s.isEmpty()) {
            throw new IllegalArgumentException("Invalid Input");
        }
        s = s.toLowerCase();
        TrieNode current = root; 
        
        for(int i=0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - 'a';
            if(current.children[index]==null) {
                TrieNode node = new TrieNode();
                // 修复下标错误
                current.children[index] = node;
                current = node;
            } else {
                current = current.children[index];
            }
        }
        current.isWord = true;
    }
    
    public boolean search(String s) {
        if(s==null || s.isEmpty()) {
            throw new IllegalArgumentException("Invalid or empty string");
        }
        s=s.toLowerCase();
        TrieNode current = root;
        for(int i=0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if(current.children[index] == null) { 
                return false;
            } else {
                current = current.children[index];
            }
        }
        return current.isWord;
    }
    
    
    public static void main(String []args) {
        trie t = new trie();
        t.insert("car");
        t.insert("cat");
        t.insert("care");
        System.out.println("Insert successful!!");
        System.out.println(t.search("car"));
    }
}

验证效果 #

修复后运行代码，输出结果为：

Insert successful!!
true

符合预期功能。

内容的提问来源于stack exchange，提问作者Niharika