Java solution with map and dfs


  • 1
    X

    Use the Map to record the legal words. we can store these words in the trie structure and use dfs to find out legal word which we check with the map and make sure the word is not prefixed. There is an easy way to do it by directly adding the leaf type in the TrieNode without using Map. (check if the last character is leaf node or not)

    class TrieNode{
    TrieNode [] children;
    public TrieNode(){
    this.children = new TrieNode[26];
    }
    }
    public class WordDictionary {

    /** Initialize your data structure here. */
    
    TrieNode root;
    Map<String,Integer> map = new HashMap<>();
    
    public WordDictionary() {
        root = new TrieNode();
    
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = root;
    	map.put(word,1);
    	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];
    		
    	}
        
    }
    
    /** 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 msearch(word, 0, root, new StringBuilder());
    
        
    }
    
    	public boolean msearch(String word, int i , TrieNode r, StringBuilder sb){
    
    	if(i == word.length()){
    		
    
    	if( !map.containsKey(sb.toString()))
    		return false;
    	return true;
    
    	}
    		
    	TrieNode node = r;
    	 
    	int index = word.charAt(i) - 'a';
    
    	if(index == -51) // means dot
    	{
    			for(int k = 0; k < 26; k++){
    				
    				if(node.children[k] == null) continue;
    				if(msearch(word, i + 1,node.children[k], sb.append((char)(k + 'a'))))
    					return true;
    				else
    				    sb.setLength(sb.length() - 1);	
    				}
    
    				
    	}
    	
    	else{
    			
        	if(node.children[index] == null){
    	    	return false;
    	    }
    	
        	else{
    	    	if(!msearch(word, i + 1, node.children[index], sb.append((char)(index +'a'))))
    		    	sb.setLength(sb.length() - 1);	
    		
    		    else {
    		    	return true;
    		    }
    	    }
    	
        }
        return false;
    }
    

    }


Log in to reply
 

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