Easy Java code beat 99%


  • 0
    L
    public class WordDictionary {
        class TrieNode {
            public TrieNode[] children = new TrieNode[26];
            public boolean isEnd;
        }
        private TrieNode root;
        
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            TrieNode ws = root;
            for(int i = 0; i < word.length(); i ++){
                if(ws.children[word.charAt(i) - 'a'] == null){
                    ws.children[word.charAt(i) - 'a'] = new TrieNode();
                }
                ws = ws.children[word.charAt(i) - 'a'];
            }
            
            ws.isEnd = true;
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public boolean search(String word) {
            return helper(root, word, 0);
        }
        
        public boolean helper(TrieNode root, String word, int pos) {
            if(root == null) {
                return false;
            }
            if(pos == word.length()) {
                return root.isEnd;
            }
            
            if(word.charAt(pos) == '.'){
                for(int i = 0; i < 26; i++){
                    if(root.children[i] != null){
                        if(helper(root.children[i], word, pos + 1)){//tricky, only helper is true, return true; otherwise, continue;
                            return true;
                        }
                    }
                }
            } else {              
                return helper(root.children[word.charAt(pos) - 'a'], word, pos + 1);
            }
            
            return false;
        }
    }
    

Log in to reply
 

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