Saved from https://leetcode.com/problems/design-add-and-search-words-data-structure/solution/

lc211

class WordDictionary {
    
    static final int ALPHABET_SIZE = 26;
      
    public static class TrieNode {
        char val;
        int count;
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
        
        TrieNode(char val) {
            this.val = val;
            this.count = 0;
        }
        
        public String toString() {
            return String.valueOf(val) + ": " + Arrays.stream(children).filter(elem -> elem != null).collect(Collectors.toList());
        }
    }
    
    private TrieNode root = new TrieNode('$');

    /** Initialize your data structure here. */
    public WordDictionary() {
        
    }
    
    public void addWord(String word) {
        TrieNode currNode = root;
        for (int i = 0; i < word.length(); i++) {
            char val = word.charAt(i);
            if (currNode.children[val - 'a'] == null) {
                currNode.children[val - 'a'] = new TrieNode(val);
            }
            currNode = currNode.children[val - 'a'];
        }
        currNode.count++;
    }
    
    public boolean search(String word) {
        assert !word.isEmpty();
        return search(word, 0, root);
    }
    
    private boolean search(String word, int idx, TrieNode parent) {
        // if reaches end, return true
        // otherwise, 
        // 1) if curr char matches currNode.val, continue moving down
        // 2) else, return false
        if (idx >= word.length()) {
            return parent.count > 0;
        }
        assert parent != null;
        char ci = word.charAt(idx);
        if (ci == '.') {
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                if (parent.children[i] != null && search(word, idx+1, parent.children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            TrieNode currNode = parent.children[ci - 'a'];
            if (currNode == null || currNode.val != ci) {
                return false;
            }
            return search(word, idx+1, currNode);
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */