在 Java 中的 Trie 数据结构中插入和搜索

Question

我写了下面的 Java 代码用于在 Java 中插入和搜索单词：

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[i] = 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"));
        
    }
}

搜索功能returns false 当前输出：
Insert successful!! false

不过我不知道哪里出了问题。我也检查了在线可用的各种资源。有什么指点吗？

Answer 1

问题是您在 insert() 函数中将 node 分配给了当前 node 的错误子项。
更改这行代码：

current.children[i] = node;

对此：

current.children[index] = node;

问题会解决的。

在 Java 中的 Trie 数据结构中插入和搜索

Insert and Search in Trie data structure in Java

java

search

insert

trie

data-structures