My JAVA Trie based solution


  • 23
    Q
    public class WordDictionary {
        WordNode root = new WordNode();
    	public void addWord(String word) {
    		char chars[] = word.toCharArray();
            addWord(chars, 0, root);
        }
    	
    	private void addWord(char[] chars, int index, WordNode parent) {
    		char c = chars[index];
    		int idx = c-'a';
            WordNode node = parent.children[idx];
            if (node == null){
            	node = new WordNode();
            	parent.children[idx]=node;
            }
            if (chars.length == index+1){
            	node.isLeaf=true;
            	return;
            }
            addWord(chars, ++index, node);
        }
    
    
        public boolean search(String word) {
        	return search(word.toCharArray(), 0, root);				     
        }
        
        private boolean search(char[] chars, int index, WordNode parent){
        	if (index == chars.length){
        		if (parent.isLeaf){
        			return true;
        		}
        		return false;
        	}
        	WordNode[] childNodes = parent.children;
        	char c = chars[index];
        	if (c == '.'){
    	    	for (int i=0;i<childNodes.length;i++){
    	    		WordNode n = childNodes[i];
    	    		if (n !=null){
    	    			boolean b = search(chars, index+1, n);
    	    			if (b){
    	    				return true;
    	    			}
    	    		}
    	    	}
    	    	return false;
        	}
        	WordNode node = childNodes[c-'a'];
        	if (node == null){
        		return false;
        	}
        	return search(chars, ++index, node);
        }
        
    
        
        private class WordNode{
        	boolean isLeaf;
        	WordNode[] children = new WordNode[26];
        }
    }

  • -24
    Z

    don't you think time complexity is too large, max time complexity will be O(26^n)


  • 0
    Q

    It only checks all 26 letters in case of '.'
    In theory you could construct a search string consisting only of '.' characters, and make the search string longer than any word in a trie. In this case every single node will be searched.
    It would still be A LOT less then O(26^n) as it's imporbable that every node has a fully filled set of child nodes.


  • 16
    E

    Thanks for sharing. Could be shorter

    public class WordDictionary {
        class TrieNode {
            TrieNode[] child = new TrieNode[26];
            boolean isWord = false;
        }
        TrieNode root = new TrieNode();
        public void addWord(String word) {
            TrieNode p = root;
            for (char c : word.toCharArray()) {
                if (p.child[c - 'a'] == null) p.child[c - 'a'] = new TrieNode();
                p = p.child[c - 'a'];
            }
            p.isWord = true;
        }
    
        public boolean search(String word) {
            return helper(word, 0, root);
        }
        
        private boolean helper(String s, int index, TrieNode p) {
            if (index >= s.length()) return p.isWord;
            char c = s.charAt(index);
            if (c == '.') {
                for (int i = 0; i < p.child.length; i++)
                    if (p.child[i] != null && helper(s, index + 1, p.child[i]))
                        return true;
                return false;
            } else return (p.child[c - 'a'] != null && helper(s, index + 1, p.child[c - 'a']));
        }
    }
    

  • 0

    @EdickCoding Very nice and short! I think my helper() as below is clean too. Thanks for sharing :)

        private boolean doSearch(TrieNode cur, char[] word, int pos) {
            if (cur == null) return false;
            if (pos == word.length) return cur.isWord;
            
            if (word[pos] == '.') {
                for (TrieNode next : cur.next)
                    if (doSearch(next, word, pos + 1))
                        return true;
                return false;
            }
            return doSearch(cur.next[word[pos] - 'a'], word, pos + 1);
        }
    

  • 0
    A

    public class WordDictionary {
    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }
        TrieNode cur = root;
        
        for (char c: word.toCharArray()) {
            if (cur.children[c-'a'] != null) {
                cur = cur.children[c-'a'];
            } else {
                cur.children[c-'a'] = new TrieNode(c);
                cur = cur.children[c-'a'];
            } 
        }
        
        cur.isLeaf = true;
    }
    
    public boolean search(String word) {
        if (word == null || word.isEmpty()) {
            return false;
        }
        return find(root, word);
    }
    
    public boolean find (TrieNode cur, String word) {
        for (int i = 0; i<word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                for (int j=0; j<26; j++) {
                    if(find(cur, (char)('a' + j) + word.substring(i+1))) {
                        return true;
                    }
                }
                return false;
            } else if (cur.children[c-'a'] != null) {
                cur = cur.children[c-'a'];
            } else {
                return false;
            } 
        }
        
        return cur.isLeaf;
    }
    
    
    class TrieNode {
        char c;
        boolean isLeaf;
        TrieNode[] children = new TrieNode[26];
        TrieNode() {}
        TrieNode(char c) {
            this.c = c;
        }
    }
    

    }


Log in to reply
 

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