Recursive Java DFS solution | Uses trie


  • 0
    M
    public class WordDictionary {
        
        Trie root;
    
        /** Initialize your data structure here. */
        public WordDictionary() {
            root = new Trie();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            
            Trie node = root;
    
    		for (char c : word.toCharArray()) {
    
    			if (node.children.containsKey(c)) {
    				node = node.children.get(c);
    			} else {
    				// Create a new Trie Node
    				Trie newNode = new Trie();
    
    				// Add the character at this node
    				node.children.put(c, newNode);
    				node = newNode;
    			}
    		}
    		node.endOfWord = 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) {
            
            Trie node = root;        
            return searchUtil(word, node);      
           
        }
        
        private boolean searchUtil(String word, Trie node) {
            
            if (word.trim().equals("")) {
                return node.endOfWord;
            }
            
            char c = word.charAt(0);
            
            if (node.children.containsKey(c)) {
                return searchUtil(word.substring(1), node.children.get(c));
            } else if (c == '.') {
                for (char _c : node.children.keySet()) {                    
                    if (searchUtil(word.substring(1), node.children.get(_c))) {
                        return true;
                    }
                }            
            }
            return false;
        }
    }
    
    class Trie {
        
        Map<Character, Trie> children;
        boolean endOfWord;
        
        public Trie() {
            children = new HashMap<Character, Trie>();
        }
    }
    

Log in to reply
 

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