public class WordDictionary {
    private class DicNode {
        boolean contains;
        Map<Character, DicNode> children;

        DicNode() {
            contains = false;
            children = new HashMap<>();
        }
    }

    private DicNode root;

    public WordDictionary() {
        root = new DicNode();
    }

    // Adds a word into the data structure.
    public void addWord(String word) {
        if (word == null || word.length() == 0)
            return;
        DicNode n = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!n.children.containsKey(c)) {
                n.children.put(c, new DicNode());
            }
            n = n.children.get(c);
        }
        n.contains = 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 search(word, root);
    }

    private boolean search(String word, DicNode root) {
        if ("".equals(word))
            return root.contains;
        char first = word.charAt(0);
        if ( first == '.' ) {
            for (DicNode n: root.children.values()) {
                if (search(word.substring(1), n))
                    return true;
            }
            return false;
        } else {
            // first != '.'
            return root.children.containsKey(first) && search(word.substring(1), root.children.get(first));
        }
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");