My java solution based on Trie Tree


  • 0
    C
    public class WordDictionary {
        private class TrieNode {
            boolean isWord = false;
            TrieNode[] children = new TrieNode[26];
        }
        
        TrieNode root;
        
        public WordDictionary() {
            root = new TrieNode();
        }
        
        // Adds a word into the data structure.
        public void addWord(String word) {
            TrieNode ws = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (ws.children[c - 'a'] == null)
                    ws.children[c - 'a'] = new TrieNode();
                ws = ws.children[c - 'a'];
            }
            ws.isWord = 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) {
            return dfsSearch(word.toCharArray(), 0, root);
        }
        
        private boolean dfsSearch(char[] word, int index, TrieNode node) {
            if (index == word.length) {
                if (node.isWord) return true;
                return false;
            }
            
            char c = word[index];
            
            if (c == '.') {
                for (int i = 0; i < 26; i++) {
                    TrieNode child = node.children[i];
                    if (child != null) {
                        if (dfsSearch(word, index + 1, child))
                            return true;
                    }
                }
                return false;
            }
            
            if (node.children[c - 'a'] == null) return false;
            return dfsSearch(word, ++index, node.children[c - 'a']);
        }
    }

Log in to reply
 

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