src/main/java/com/stevesun/solutions/_211.java

package com.stevesun.solutions;

/**
 * Design a data structure that supports the following two operations:

 void addWord(word)
 bool search(word)
 search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

 For example:

 addWord("bad")
 addWord("dad")
 addWord("mad")
 search("pad") -> false
 search("bad") -> true
 search(".ad") -> true
 search("b..") -> true
 Note:
 You may assume that all words are consist of lowercase letters a-z.

 You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
 */
public class _211 {
    public class WordDictionary {
        WordNode root = new WordNode();

        public void addWord(String word) {
            char chars[] = word.toCharArray();
            addWord(chars, 0, root);
        }

        private void addWord(char[] chars, int index, WordNode parent) {
            char c = chars[index];
            int idx = c - 'a';
            WordNode node = parent.children[idx];
            if (node == null) {
                node = new WordNode();
                parent.children[idx] = node;
            }
            if (chars.length == index + 1) {
                node.isLeaf = true;
                return;
            }
            addWord(chars, ++index, node);
        }

        public boolean search(String word) {
            return search(word.toCharArray(), 0, root);
        }

        /**This is also a beautifully designed recursive function.*/
        private boolean search(char[] chars, int index, WordNode parent) {
            if (index == chars.length) {
                if (parent.isLeaf) {
                    return true;
                }
                return false;
            }
            WordNode[] childNodes = parent.children;
            char c = chars[index];
            if (c == '.') {
                for (int i = 0; i < childNodes.length; i++) {
                    WordNode n = childNodes[i];
                    if (n != null) {
                        boolean b = search(chars, index + 1, n);
                        if (b) {
                            return true;
                        }
                    }
                }
                return false;
            }
            WordNode node = childNodes[c - 'a'];
            if (node == null) {
                return false;
            }
            return search(chars, ++index, node);
        }

        /**This is a cool/standard design for a Trie node class.*/
        private class WordNode {
            boolean isLeaf;
            WordNode[] children = new WordNode[26];
        }

    }

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