Solution sharing - Java beats 89% simple


  • 0
    M
    public class Trie {
    
        /** Initialize your data structure here. */
        public boolean isWord = false;
        private Trie[] children;
        
        public Trie() {
            children = new Trie[26];
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
            Trie node = this;
            for(int i=0;i<word.length();i++){
                if(node.children[word.charAt(i) - 'a'] == null){
                    node.children[word.charAt(i) - 'a'] = new Trie();
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            node.isWord = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            if(word == null || word.length() < 1){
                return false;
            }
            Trie node = this.children[word.charAt(0) - 'a'];
            if(node == null){
            	return false;
            }
            for(int i=1;i<word.length();i++){
                if(node.children[word.charAt(i) - 'a'] == null){
                    return false;
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            return node.isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            if(prefix == null || prefix.length() < 1){
                return false;
            }
            Trie node = this.children[prefix.charAt(0) - 'a'];
            if(node == null){
            	return false;
            }
            for(int i=1;i<prefix.length();i++){
                if(node.children[prefix.charAt(i) - 'a'] == null){
                    return false;
                }
                node = node.children[prefix.charAt(i) - 'a'];
            }
            return true;
        }
    }
    

Log in to reply
 

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