211. Add and Search Word - Data structure design (Medium)

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 lettersa-zor.. 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 lettersa-z.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Solution 1: Trie

We can use the data structure Trie. First, we need to define a TrieNode class, which has 2 properties.
a TrieNode array, In this problem, only lower-case letters a - z need to be considered, so each TrieNode has at most 26 children and the array's size is 26.
a boolean value to record if current node is the final node of a word. (if the string comprised of characters starting from root to the current node is a word.)
For addWord(), the basic idea is to create a TrieNode corresponding to each letter in the word. When we are done, label the last node to be a word.

    class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord = false;
    }

    private TrieNode root;

    // initialize your data structure here.
    public WordDictionary() { // In the constructor, we initialize the root node.
        root = new TrieNode();
    }

    // Adds a word into the data structure.
    public void addWord(String word) { //Iterative O(n);O(1)
        if (word == null) {
            return;
        }

        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            if (node.children[word.charAt(i) - 'a'] == null) {
                node.children[word.charAt(i) - 'a'] = new TrieNode();
            }
            node = node.children[word.charAt(i) - 'a'];
        }
        node.isWord = true;
    }

    // Returns if the word is in the data structure. 
    // A word could contain the dot character '.' to represent any one letter.
    /**
     * Recursive. O(n); O(n)
     * Base case: If start pointer reaches the string's end, check the node's flag. 
     * If true, there is a word, return true.
     * To handle '.'.
     * If the character is not a dot:
     * | Check if the next node is null, if yes, return false.
     * | If not, go on to the next node.
     * If the character is a dot, it can match any letter.
     * That means we must search every possible subtree/subtrie.
     * | So for each child of current node, search the rest characters of the word.
     * | If there is one match, return true.
     * If there is no match at all, return false.
     */    
    public boolean search(String word) {
        if (word == null) {
            return false;
        }

        return match(word, 0, root);
    }

    private boolean match(String word, int start, TrieNode node) {
        if (start == word.length()) {
            return node.isWord;
        }

        if (word.charAt(start) != '.') {
            return node.children[word.charAt(start) - 'a'] != null
                    && match(word, start + 1, node.children[word.charAt(start) - 'a']);
        } else {
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i] != null && match(word, start + 1, node.children[i])) {
                    return true;
                }
            }
        }
        return false;
    }

Follow Up:

1.如何优化

在原本的trieNode class中加入一个length的int，记录每个单词的长度，如果匹配单词的长度大于了记录的，就false了
问题是如果记录的是一个较短的单词呢，只是匹配单词的前面一部分？还是得遍历完整个字符串。

2.给定一个字典，查询字符串，要支持类似于“book”, "book...", "..boo.."，这种查询

建立tire tree，然后递归查询，follow up是，如果模糊查询只有"...book"和“book...”这两种模式怎么处理，

回答，只要建立顺序tire树，反序tire树，就可以了。

3.一道tag题，加上长时间的讨论data structure for 字典，题目不难，followup问的很细，很基础，考察到了trie

4.