Java solution using Trie


  • 0
    M
    public class WordDictionary {
        
        class TrieNode{
            boolean isLeaf;
            TrieNode[] children;
            TrieNode(){
                isLeaf = false;
                children = new TrieNode[26];
            }
        }
        
        TrieNode root = new TrieNode();
        
    	// Adds a word into the data structure.
    	public void addWord(String word) {
    		insert(word, root);
    	}
    	
    	private void insert(String word, TrieNode node) {
    		for (int i = 0; i < word.length(); i++) {
    			int index = word.charAt(i) - 'a';
    			if (node.children[index] == null) {
    				node.children[index] = new TrieNode();
    			}
    			node = node.children[index];
    		}
    		node.isLeaf = 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 searchWord(word, 0, root);
    	}
    
    	private boolean searchWord(String word, int index, TrieNode node) {
    		if (node == null) return false;
    		if(index == word.length()) return node!=null && node.isLeaf;
    		char c = word.charAt(index);
    		if (c == '.') {
    			for (int j = 0; j < 26; j++) {
    				if (searchWord(word, index + 1, node.children[j]) )
    					return true;
    			}
    		} else { // a~z
    			if (searchWord(word, index+1, node.children[c-'a']))
    				return true;
    			}
    		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.