Java Trie Solution (recursive)


  • 0
    A
    public class WordDictionary {
        
        private static class TrieNode {
            public boolean end;
            public Map<Character, TrieNode> children = new HashMap<>();
            
            public TrieNode(boolean end) {
                this.end = end;
            }
        }
        
        private TrieNode root = new TrieNode(false);
    
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode current = root;
            int n = word.length();
            for (int i = 0; i < n; i++) {
                char c = word.charAt(i);
                if (current.children.containsKey(c)) {
                    current = current.children.get(c);
                    if (i == n -1) {
                        current.end = true;
                    }
                }
                else {
                    TrieNode node = new TrieNode(i == n - 1);
                    current.children.put(c, node);
                    current = node;
                }
            }
        }
    
        // 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 search(word, root);
        }
        
        private boolean search(String word, TrieNode node) {
            if (word == null || (word.isEmpty())) {
                return node.end;
            }
            char c = word.charAt(0);
            if (c != '.') {
                if (!node.children.containsKey(c)) {
                    return false;
                }
                else {
                    return search(word.substring(1), node.children.get(c));
                }
            }
            else {
               // Collection<TrieNode> children = node.children.values();
                for (TrieNode child : node.children.values()) {
                    if (search(word.substring(1), child)) {
                        return true;
                    }  
                }
                return false;
            }
        }
    }
    
    // Your WordDictionary object will be instantiated and called as such:
    // WordDictionary wordDictionary = new WordDictionary();
    // wordDictionary.addWord("word");
    // wordDictionary.search("pattern");

Log in to reply
 

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