Add and Search Word

Problem

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.

Solution

class WordDictionary {

    class TrieNode {
        TrieNode[] children;
        boolean endOfWord;
        public TrieNode() {
            this.children = new TrieNode[26];
            this.endOfWord = false;
        }
    }

    private TrieNode root;

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

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.children[ch - 'a'] == null) cur.children[ch - 'a'] = new TrieNode();
            cur = cur.children[ch - 'a'];
        }
        cur.endOfWord = 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 helper(root, word.toCharArray(), 0);
    }

    private boolean helper(TrieNode cur, char[] chars, int index) {
        if (index == chars.length) return cur.endOfWord;
        char ch = chars[index];
        if (ch != '.') return cur.children[ch - 'a'] != null && helper(cur.children[ch - 'a'], chars, index + 1);
        else {
            for (int i = 0; i < 26; i++) {
                if (cur.children[i] != null && helper(cur.children[i], chars, index + 1)) return true; 
            }
        }
        return false;
    }
}

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

Analysis

The idea is from Implement Trie
To deal with '.' in calling search() method, we use recursion to return correct result
That is, if current char is '.', we check each TrieNode from the cur.children
Notice that before recursively calling helper() method, do not forget to check if current child is null