Clean Java Trie Solution (23ms)


  • 1
    public class WordDictionary {
        
        class TrieNode {
            String word = null;
            TrieNode[] children = new TrieNode[26];
        }
        
        TrieNode root = new TrieNode();
    
        public void addWord(String word) {
            TrieNode pNode = root;
            for(char c : word.toCharArray()) {
                if(pNode.children[c-'a']==null) {
                    TrieNode node = new TrieNode();
                    pNode.children[c-'a'] = node;
                }
                pNode = pNode.children[c-'a'];
            }
            pNode.word = word;
        }
        
        private boolean searchHelper(String word, TrieNode pNode) {
            for(int i=0; i<word.length(); i++) {
                char c = word.charAt(i);
                if(c!='.') {
                    pNode = pNode.children[c-'a'];
                    if(pNode==null)
                        return false;
                } else {
                    String wordTail = word.substring(i+1);
                    for(TrieNode node : pNode.children)
                        if(node!=null && searchHelper(wordTail, node))
                              return true;
                    return false; // no need to continue, cause the tail of word has been processed
                }
            }
            return pNode.word!=null;
        }
    
        public boolean search(String word) {
            return searchHelper(word,root);
        }
    }

Log in to reply
 

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