public class WordDictionary {
    TrieNode root = new TrieNode();
    /** Initialize your data structure here. */
    public WordDictionary() {

    }

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