Concise AC java solution using TrieNode (Prefix node)


  • 0
    B

    I was solving this problem before meeting this one:
    https://leetcode.com/problems/implement-trie-prefix-tree/

    It really costs me a lot of time, but after knowing what Prefix tree is, the problem turns to a easy backtracking question, and here is the accepted code:

    public class WordDictionary {
    TrieNodeTemp root = new TrieNodeTemp();
    // Adds a word into the data structure.
    public void addWord(String word) {
       TrieNodeTemp tn = root;
        for(char c : word.toCharArray()){
        	if(tn.trie[c-'a']==null) tn.trie[c-'a'] = new TrieNodeTemp();
        	tn = tn.trie[c-'a'];
        }
        tn.isWord = 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) {
        TrieNodeTemp tn = root;
        for(int i=0;i<word.length();i++){
        	char c = word.charAt(i);
        	if(c=='.') return searchHelper(tn,word.substring(i));
        	else{
        		if(tn.trie[c-'a']==null)
        			return false;
        		tn = tn.trie[c-'a'];
        	}
        }
        return tn.isWord;
    }
    
     public boolean searchHelper(TrieNodeTemp tn, String word){
        if(word.length()==0) return tn.isWord;
    	if(word.charAt(0)=='.'){
    		for(int i=0;i<26;i++){
    			if(tn.trie[i]!=null){
    				if(searchHelper(tn.trie[i], word.substring(1))) return true;
    			}		
    		}
    		return false;
    	}else{
    		if(tn.trie[word.charAt(0)-'a']!=null) return searchHelper(tn.trie[word.charAt(0)-'a'],word.substring(1));
    		else return false;
    	}
     }
    }
    
    
    class TrieNodeTemp{
    	public TrieNodeTemp[] trie = new TrieNodeTemp[26];
    	public boolean isWord;
    	public TrieNodeTemp(){};	
    }
    

  • 0
    T

  • 0
    B

    Thank you for pointing out that, I didn't know substring turns to linear since java 7u6. I guess I should use the whole word string rather than substring to reduce time complexity.


  • 0
    T

    Yep, it's easy to add int start to helper and do charAt(start) and recursive calls with start+1, also end condition becomes start == length.


Log in to reply
 

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