Clean Java Solution Based on Trie (25ms)


  • 0
    Z
    
    public class WordDictionary {
    	
        class TrieNode{
            String str;
    	TrieNode[] subNodes;
    	public TrieNode(){
    	    this.str = "";
    	    this.subNodes = new TrieNode[26];
    	}
        }
    	
        TrieNode root;
    	
        public WordDictionary(){
    	this.root = new TrieNode();
        }
        // Adds a word into the data structure.
        public void addWord(String word) {
            if(word == null || word.length() == 0){
    	    return;
    	}
    	TrieNode node = root;
    	    for(char c : word.toCharArray()){
    	    	if(node.subNodes[c - 'a'] == null){
    		    node.subNodes[c - 'a'] = new TrieNode();
    		}
    		node = node.subNodes[c - 'a'];
    	    }
    	    node.str = word;
         }
    
        // 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) {
            TrieNode node = root;
    	   return search(word, 0, node);
        }
    	
        public boolean search(String word, int pos, TrieNode node){
    	if(pos == word.length()){
    	    return (node.str.length() == pos);
    	}
    	char c = word.charAt(pos);
    	if(c == '.'){
    	    for(TrieNode subNode : node.subNodes){
    		if(subNode != null && search(word, pos+1,subNode)){
    		    return true;
    		}
    	    }
    	}
    	else if(node.subNodes[c - 'a'] != null){
    	    return search(word, pos+1,node.subNodes[c - 'a']);
    	}
    	return false;
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");
    
    

Log in to reply
 

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