Java 19ms solution (modified trie solution)


  • 8
    N

    1、use HashMap to categorized words by length.

      Map<Integer,TrieNode>trieMap = new HashMap<Integer,TrieNode>();
    

    2、all words of the same length are put in to a trie.

    In a normal trie solution,we can only search one letter per time,

    however,there are many cases where letters are continuously the same, say "caaaab"

    so we can condense these continuously duplicated letters into one trie node instead of multiple trie node

    Here is how TrieNode is defined:

    class TrieNode{
    	TrieNode children[];
    	int len = 0;  //record the number of character that is continuously duplicated
    	public TrieNode(){
    		children = new TrieNode[26];
    	}
    }
    

    this helps to reduce the trie height and the search path

    PS:

    I was able to beat 100% percent of java submission( about 15ms) just using a small trick

    Change the type of trieMap to an array

    TrieNode[]trieMap = new TrieNode[512];  //the maximum length of all testd words is about 500

  • 0
    R

    Could you type your completed code to us? Since I am really interested in what you said, I want to study your method. Thank you so much!


  • 0
    N

    Well, the whole idea is simple. But the tricky part is how to add and search a condensed node in a trie.

    Although,i have a working implementation, but it seems a bit "ugly".

    If you still insist that i post the code here, i will do it later.

    But I'm still looking forward to a better implementation or solution.

    If you have any, please do share.


  • 0
    E

    I don't quite follow you. Could you please explain what your len is used for? For example, if we have a, aa, aaa, aaaa, aaab in the trie, what are the values of len at the root node and at root's next node? It would be really helpful if you post your code here :)


  • 0
    N

    the "len" (which means the number of letters that are continuously the same) can help us to leap several letters forward instead of one letter per time.

    However, the "len" may not be the maximum leap.

    For example, abbbc and abbcd in a trie is:

    a(len=1)b(len=2)b(len=1)c(len=1)
    a(len=1)b(len=2)c(len=1)d(len=1)
    We can only leap 2 letters at b instead of 3 letters

    And there could be worse case if we put abcde into the trie, the trie will become:
    a(len=1)b(len=1)b(len=1)b(len=1)c(len=1)
    a(len=1)b(len=1)b(len=1)c(len=1)d(len=1)
    a(len=1)b(len=1)c(len=1)d(len=1)e(len=1)

    So, its worst case will be just like a normal trie(require extra space to store "len").

    in your case, we will construct 4 trie (first categorized by length of string)

    1. length=1 : a(len=1)
    2. length=2 : a(len=2)
    3. length=3 : a(len=3)
    4. length=4 : a(len=3)a(len=1) , a(len=3)b(len=1)

  • 0
    N

    This is the original working solution(imporvement is needed).

    PS, it will take some time and patience to understand the code, so be prepared

    Besides, feel free to modify or comment.

    static final char DOT = '.';
    //you can use more general-purpose datastructure like hashmap
    final TrieNode[]trieMap = new TrieNode[512]; //maximum length of words tested is 500!let's hack it
    class TrieNode{
    	TrieNode children[];
    	int len = 0;  //number of letters that are continuously duplicate
    	public TrieNode(){
    		children = new TrieNode[26];
    	}
    }
    

    method add word

     public void addWord(String word) {
    	char[]letters = word.toCharArray();
    	TrieNode curNode = null,childNode = null;
    	curNode = trieMap[letters.length];
    	if(curNode==null){
    		curNode = new TrieNode();
    		trieMap[letters.length] = curNode;
    	}
    	int idx = 0;
    	char letter = ' ';
    	int continuousLen = 1;
    	for (int i=0;i<letters.length;i++){
    		letter = letters[i];
    		continuousLen = 1;
    		while(i<letters.length-1 && letters[i+1]==letter){
    			continuousLen ++;
    			i++;
    		}
    		idx = letter -'a';
    		childNode = curNode.children[idx];
    		if (childNode==null){
    			childNode = new TrieNode();
    			curNode.children[idx] = childNode;
    			childNode.len = continuousLen;
    		}else{
    			if(continuousLen>childNode.len){
    				continuousLen -= childNode.len;
    				while(childNode.children[idx]!=null){
    					childNode = childNode.children[idx];
    					if(childNode.len<continuousLen){
    						continuousLen -= childNode.len;
    					}else if(childNode.len>continuousLen){
    						TrieNode n = new TrieNode();
    						n.len = childNode.len-continuousLen;
    						TrieNode cTmp[] = n.children;
    						n.children = childNode.children;
    						childNode.children = cTmp;
    						childNode.len = continuousLen;
    						childNode.children[idx] = n;
    						n = null;
    						continuousLen = 0;
    						break;
    					}else{
    						continuousLen = 0;
    						break;
    					}
    				}
    				if(continuousLen>0){
    					TrieNode n = new TrieNode();
    					n.len = continuousLen;
    					childNode.children[idx] = n;
    					childNode = n;
    				}
    			}else if(continuousLen<childNode.len){ // split
    				TrieNode n = new TrieNode(); 
    				n.len = childNode.len-continuousLen;
    				TrieNode cTmp[] = n.children;
    				n.children = childNode.children;
    				childNode.children = cTmp;
    				childNode.children[idx] = n;
    				childNode.len = continuousLen;
    			}
    		}
    		curNode = childNode;
    	}
    }
    

    method search word

    private boolean searchPrefix(char[]letters,int start,int end,int continuousLen,TrieNode root){
    	if(root==null)return false;
    	if(start>=end)return true;
    	char letter = letters[start];
    	if(letter==DOT){
    		for(int c = 0;c<26;c++){
    			TrieNode child = root.children[c];
    			if(child!=null){
    				if(child.len>1){
    					continuousLen = 1;
    					int s = start;
    					while(s+1<end && (letters[s+1]==DOT || letters[s+1]-'a'==c)){
    						s++;
    						continuousLen++;
    					}
    					if(continuousLen>=child.len){
    						continuousLen -= child.len;
    						if(searchPrefix(letters,start+child.len,end,continuousLen,child)){
    							return true;
    						}
    					}
    				}else if(searchPrefix(letters,start+1,end,continuousLen,child)){
                		return true;
    				}
    			}
            }
    	}else{
    		int s = start,idx = letter-'a';
    		if(continuousLen<1){
        		continuousLen = 1;
        		while(s+1<end && letters[s+1]==letter){
        			s++;
        			continuousLen++;
        		}
    		}
    		TrieNode child = root.children[idx];
    		if(child!=null && continuousLen>1){
    			if(continuousLen>=child.len){
    				return searchPrefix(letters,start+child.len,end,continuousLen-child.len,child);
    			}else{
    				int dotLen = 0;
    				s = start+continuousLen;
    				while(s<end && letters[s]==DOT){
    					s++;
    					dotLen++;
    				}
    				if(continuousLen+dotLen<child.len){
    					return false;
    				}else{
    					return searchPrefix(letters,start+child.len,end,0,child);
    				}
    			}
    		}else{
    			return searchPrefix(letters,start+1,end,0,child);
    		}
    	}
    	return false;
    }
    

    main search method

    public boolean search(String word) {
    	char[]letters = word.toCharArray();
    	TrieNode root = trieMap[letters.length];
    	return searchPrefix(letters,0,letters.length,0,root);
    }

Log in to reply
 

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