Easy java solution using trie


  • 0
    public TrieNode root = new TrieNode();
    Map<String, Boolean> memo = new HashMap<>();
    
    // Adds a word into the data structure.
    public void addWord(String word) {
        if(memo.containsKey(word) && memo.get(word)) return;
        TrieNode tmp = root;
        for(int i=0; i<word.length(); i++) {
            char c = word.charAt(i);
            if(tmp.children[c-'a'] == null) tmp.children[c-'a'] = new TrieNode();
            tmp = tmp.children[c-'a'];
        }
        tmp.isEnd = true;
        memo.put(word, 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) {
        if(memo.containsKey(word)) return memo.get(word);
        return dfs(word, 0, root);
    }
    
    private boolean dfs(String word, int index, TrieNode tmp) {
        if(tmp == null) return false;
        char c = word.charAt(index);
        if(index == word.length()-1) {
            if(c != '.') return tmp.children[c-'a'] != null && tmp.children[c-'a'].isEnd;
            else {
                for(int i=0; i<26; i++) {
                    if(tmp.children[i] != null && tmp.children[i].isEnd) return true;
                }
                return false;
            }
        }
    
        if(c != '.') {
            if(tmp.children[c-'a'] == null) return false;
            return dfs(word, index+1, tmp.children[c-'a']);
        } else {
            for(int i=0; i<26; i++) {
                if(tmp.children[i] == null) continue;
                if(dfs(word, index+1, tmp.children[i])) return true;
            }
            return false;
        }
    }
    
    class TrieNode {
        boolean isEnd;
        TrieNode[] children;
        public TrieNode() {
            this.isEnd = false;
            this.children = new TrieNode[26];
        }
    }

Log in to reply
 

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