Java Trie With Recursion


  • 0
    A
    public class WordDictionary {
    
        private static class TrieNode {
            private static final int MAX_LINKS = 26;
    
            private TrieNode[] links;
            private boolean end;
    
            public TrieNode() {
                links = new TrieNode[MAX_LINKS];
                end = false;
            }
    
            public boolean containsKey(final char ch) {
                return links[ch - 'a'] != null;
            }
    
            public TrieNode get(final char ch) {
                return links[ch - 'a'];
            }
    
            public void put(final char ch, final TrieNode node) {
                links[ch - 'a'] = node;
            }
    
            public boolean isEnd() {
                return end;
            }
    
            public void setEnd() {
                this.end = true;
            }
        }
    
        private TrieNode root;
    
        public WordDictionary() {
            root = new TrieNode();
        }
    
        /** Adds a word into the data structure. */
        public void addWord(final String word) {
            TrieNode current = root;
            for (char ch : word.toCharArray()) {
                if (!current.containsKey(ch)) {
                    current.put(ch, new TrieNode());
                }
                current = current.get(ch);
            }
            current.setEnd();
        }
    
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public boolean search(final String word) {
            char[] chars = word.toCharArray();
            return searchHelper(chars, 0, root);
        }
    
        private boolean searchHelper(final char[] chars, final int index, final TrieNode current) {
            if (index == chars.length) {
                return current.isEnd();
            } else {
                char ch = chars[index];
                if (ch != '.') {
                    if (current.containsKey(ch)) {
                        return searchHelper(chars, index+1, current.get(ch));
                    } else {
                        return false;
                    }
                } else {
                    for (char replacement = 'a'; replacement <= 'z'; replacement++) {
                        if (current.containsKey(replacement)) {
                            if (searchHelper(chars, index+1, current.get(replacement))) {
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }
    }
    

Log in to reply
 

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