Ac solution code


  • 0

    The solution is based on Trie, and the only trick is that if meet '.', check parent's children 'a'-'z'.

    Time complexity(Add, Search) = O(keyLength)

    JAVA Code:

    public class WordDictionary {
    	private wordNode root = new wordNode();
    	public boolean search(String word) {
    		return search(word.toCharArray(), 0, root);
    	}
    	
    	public boolean search(char chs[], int index, wordNode parent) {		
    		if (parent == null) return false; 
    		if (index == chs.length) return parent.isLeaf;
    				 
    		char ch = chs[index];
    		if (ch == '.') {// If meet '.', check parent's children 'a'-'z'
    			for (int i = 0; i < 26; i++) {
    				if (search(chs, index + 1, parent.children[i]))
    					return true;
    			}
    			return false;
    		} else {// If meet 'a'-'z'
    			if (parent.children[ch-'a'] == null)
    				return false;
    			return search(chs, index + 1, parent.children[ch-'a']);
    		}		
    	} 
    	
    	public void addWord(String word) {
    		wordNode cur = root;
    		for (char ch : word.toCharArray()) {// Append characters to the trie's branches
    			if (cur.children[ch-'a'] == null)
    				cur.children[ch-'a'] = new wordNode();
    			cur = cur.children[ch-'a'];
    		} 
    		cur.isLeaf = true;// Reach the leaf
    	}
    }
    
    class wordNode {
    	public boolean isLeaf;
    	public wordNode children[];
    	public wordNode(){ children = new wordNode[26];};
    };

Log in to reply
 

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