Java solution


  • 0
    M
    public class Trie {
        
        class TrieNode{
            TrieNode[] children;
            boolean isLeaf;
            public TrieNode(){
                children = new TrieNode[26];
                isLeaf = false;
            }
        }
        
        private TrieNode root;
        
        /** Initialize your data structure here. */
        public Trie() {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            TrieNode p = root;
            for(int i=0; i<word.length(); i++){
                int idx = word.charAt(i) - 'a';
                if(p.children[idx]==null) p.children[idx] = new TrieNode(); //!!注意判断p[idx]==null
                p = p.children[idx];
            }
            p.isLeaf = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            TrieNode node = searchWord(word);
            return node!=null && node.isLeaf;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            TrieNode node = searchWord(prefix);
            return node != null;
        }
        
        private TrieNode searchWord(String word){
            TrieNode p = root;
            for(int i=0; i<word.length(); i++){
                int idx = word.charAt(i) - 'a';
                if(p.children[idx]==null) return null;
                p = p.children[idx];
            }
            return p;
        }
    }
    

Log in to reply
 

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