Trie Implement with out redundant var


  • 0
    F
    class Trie {
        private final int SIZE = 26;
        private Node root;       // 字典树的根结点
        
        class Node {
            Node[] children;
            boolean isStr;
            
            public Node() {
                children = new Node[SIZE];
                isStr = false;
            }
        }
    
        
    
        /** Initialize your data structure here. */
        public Trie() {
            root = new Node();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            Node pointer = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (pointer.children[index] == null) {
                    pointer.children[index] = new Node();
                }
                pointer = pointer.children[index];
            }
            pointer.isStr = true;
            
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            Node pointer = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (pointer.children[index] == null 
                   || (i + 1 == word.length() && pointer.children[index].isStr == false)) {
                    return false;
                }
                pointer = pointer.children[index];
            }
            return true;
            
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            Node pointer = root;
            for (int i = 0; i < prefix.length(); i++) {
                int index = prefix.charAt(i) - 'a';
                if (pointer.children[index] == null) {
                    return false;
                }
                pointer = pointer.children[index];
            }
            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);
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.