Leetcode 208. 实现 Trie (前缀树)

题目

https://leetcode.cn/problems/implement-trie-prefix-tree/

Java AC

    class Node{
    
        char c;
        Node[] next;
        boolean finished;
    }
class Trie {
    

    public Node root;
    public Trie() {
    
    
        root = new Node();
    }
    
    public void insert(String word) {
    
        Node currentNode = root;
        for(int i=0;i<word.length();i++){
    
            char c = word.charAt(i);
            int index = (int)(c-'a');
           // System.out.println(0);
            if(currentNode.next==null){
    
                currentNode.next = new Node[26];
            }
            
            if(currentNode.next[index]==null){
    
                Node t = new Node();
                currentNode.next[index] = t;
            }
            currentNode = currentNode.next[index];
            currentNode.c = c;
        }
        currentNode.finished = true;
    }
    
    public boolean search(String word) {
    
        Node currentNode = root;
        for(int i=0;i<word.length();i++){
    
            char c = word.charAt(i);
            int index = (int)(c-'a');
            if(currentNode.next==null || currentNode.next[index]==null){
    
                return false;
            }
            currentNode = currentNode.next[index];
            if(i==word.length()-1){
    
                return currentNode.finished;
            }
        }
        return false;
    }
    
    public boolean startsWith(String prefix) {
    
        Node currentNode = root;
        for(int i=0;i<prefix.length();i++){
    
            char c = prefix.charAt(i);
            int index = (int)(c-'a');
            if(currentNode.next==null ||currentNode.next[index]==null){
    
                return false;
            }
            currentNode = currentNode.next[index];
            if(i==prefix.length()-1){
    
                return true;
            }
        }
        return true;
    }
}

/** * Your Trie object will be instantiated and called as such: * Trie obj = new Trie(); * obj.insert(word); * boolean param_2 = obj.search(word); * boolean param_3 = obj.startsWith(prefix); */