Java Recursive Hashmap solution


  • 0
    R

    class WordDictionary {

    private class WordTrieNode{
        Map<Character, WordTrieNode> children;
        boolean endOfWord; 
        public WordTrieNode(){
            children = new HashMap<>();
            endOfWord = false;
        }
    }
    
    private WordTrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new WordTrieNode(); 
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        addWordRecursive(root, word, 0);
    }
    
    private void addWordRecursive(WordTrieNode current, String word, int index){
        if (index == word.length()){
            current.endOfWord = true;
            return;
        }
        
        char ch = word.charAt(index);
        WordTrieNode node = current.children.get(ch);
        
        if (node==null){
            node = new WordTrieNode();
            current.children.put(ch,node);
        }
        addWordRecursive(node,word,index+1);
        
    }
    
    
    /** 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 searchRecursive(root,word,0);
    }
    
    private boolean searchRecursive(WordTrieNode current, String word, int index){
        if(index == word.length()){
            return current.endOfWord;
        }
        
        char ch = word.charAt(index);
        if (ch == '.') { //. can match any character
            //iterate all children 
           
            for(WordTrieNode nodetemp: current.children.values()){
                if (nodetemp!=null && searchRecursive(nodetemp, word, index+1))
                    return true;
            }return false;    
            
        }else{
            WordTrieNode node = current.children.get(ch);
            if (node == null){
                return false;
            } 
            return searchRecursive(node, word, index+1);
        }       
    }
    

    }

    /**

    • Your WordDictionary object will be instantiated and called as such:
    • WordDictionary obj = new WordDictionary();
    • obj.addWord(word);
    • boolean param_2 = obj.search(word);
      */

Log in to reply
 

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