My Simple and clean Java code with Trie solution, 26ms.


  • 0
    S

    Trie solution

    public class WordDictionary {
        
        // build a Trie class here
        class TrieNode {
            TrieNode[] childNodes;
            public char nodeChar;
            public boolean isWord;
        
            public TrieNode() {
                childNodes = new TrieNode[26];
            }
        }
        
        private TrieNode root;
        
        public WordDictionary() {
            root = new TrieNode();
        }
    
        // Adds a word into the data structure. // Add the word into trie.
        public void addWord(String word) {
            if (word.length() == 0) return;
            TrieNode cur = root;
            
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                if(cur.childNodes[c - 'a'] == null){
                    cur.childNodes[c - 'a'] = new TrieNode();
                    cur.childNodes[c - 'a'].nodeChar = c;
                }
                cur = cur.childNodes[c - 'a'];
            }
            cur.isWord = 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 search(word,root);
        }
        
        public boolean search(String word, TrieNode node){
            TrieNode cur = node; 
            for(int i = 0; i < word.length(); i++){
                char c = word.charAt(i);
                // 'if contains an '.', need to check every childnode of current node, use recursion.
                if (c == '.'){
                    String nextWord = word.substring(i+1);
                    for(int j = 0; j < 26; j++){
                        boolean judge = false;
                        if(cur.childNodes[j]!= null){
                             judge = search(nextWord,cur.childNodes[j]);
                        }
                        if (judge == true) return true;
                    }
                    return false;
                }
                else{
                    if(cur.childNodes[c - 'a'] == null) return false;
                    cur = cur.childNodes[c - 'a'];
                }
            }
            return cur.isWord;
        }
    }
    

Log in to reply
 

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