Concise Java recursive solution and OOD.


  • 0
    Z

    simple way to use the implement Trie tree method.

    class WordDictionary {
    
        /** Initialize your data structure here. */
        
        private class TrieNode {
            private TrieNode[] next;
            private final int R = 26;
            private boolean isEnd = false;
            public TrieNode() {
                next = new TrieNode[R];
            }
            public boolean containsKey(char c) {
                return next[c - 'a'] != null;
            }
            public TrieNode get(char c) {
                return next[c - 'a'];
            }
            public void put(char c, TrieNode node) {
                next[c - 'a'] = node;
            }
            public boolean isEnd() {
                return isEnd;
            }
            public void setEnd() {
                isEnd = true;
            }
        }
        
        TrieNode root;
        
        public WordDictionary() {
            root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void addWord(String word) {
            TrieNode curr = root;
            char[] arrs = word.toCharArray();
            for (int i = 0; i < arrs.length; i++) {
                if (!curr.containsKey(arrs[i])) {
                    curr.put(arrs[i], new TrieNode());
                }
                curr = curr.get(arrs[i]);
            }
            curr.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(String word) {
            TrieNode curr = root;
            char[] arrs = word.toCharArray();
            return searchHelper(arrs, 0, curr);
        }
        
        private boolean searchHelper(char[] arrs, int id, TrieNode curr) {
            if (id == arrs.length) return curr.isEnd();
            if (arrs[id] != '.') {
                if (!curr.containsKey(arrs[id])) return false;
                return searchHelper(arrs, id + 1, curr.get(arrs[id]));
            }
            for (int i = 0; i < curr.next.length; i++) {
                if(curr.next[i] != null && searchHelper(arrs, id + 1, curr.next[i])) {
                    return true;
                }
            }
            return false;
        }
        
    }
    

Log in to reply
 

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