二刷211. Add and Search Word - Dat

讲解很棒：https://www.youtube.com/watch?v=8d_HdK0f2B4
真的是要感谢YouTube上这些分享讲解的作者，解决了我很多问题。
这个题除了search里面word可能包含通配符，其他都跟208. Implement Trie (Prefix Tree)差不多，所以我只说一下这里的find.

这里的find因为可以用b*d这样的word去搜索，所以我们要处理这种情况。其实很简单，遇到*, 我们直接跳过，然后在*这个node的孩子里去搜索b*d这个word里*后面的部分，这里就是d. 于是我们只需要判断该char== *?然后用int startIndex来标记开始找的单词substring, 遇到*就在当前节点的孩子里找剩下的substring，对应的代码是:

 if (word.charAt(index) == '.'){
        for (TrieNode temp : node.children){
            if (temp != null && find(word, temp, index + 1)){
                return true;
            }
        }
        return false;
  }

而对待不是*的部分就是正常的dfs逐层深入了，先找到char对应的孩子index j, 然后看这个孩子是否为空，为空就说明我们从来没有insert 过要搜索的这个词。不为空我们还要在当前node的孩子里继续检查后面的substring， 我们通过开始访问的char的index index 来做这件事情。并且每次find开始，记得检查index == word.length(). 如果是的话说明我们已经找到了这个词，但不能直接返回true, 还要看node.isWord. 比如我们insert的是badass, 你搜索bad, 是应该返回false的而不是true.

class WordDictionary {
    class TrieNode{
        TrieNode[] children;
        boolean isWord;
        String word;
        public TrieNode(){
            children = new TrieNode[26];
            isWord = false;
        }
    }
    TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++){
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null){
                p.children[index] = new TrieNode();
            }
            p = p.children[index];
        }
        p.isWord = true;
        p.word = word;
    }
    
    /** 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, root, 0);    
    }
    
    private boolean find(String word, TrieNode node, int index){
        if (index == word.length()){
            return node.isWord;
        }
        if (word.charAt(index) == '.'){
            for (TrieNode temp : node.children){
                if (temp != null && find(word, temp, index + 1)){
                    return true;
                }
            }
            return false;
        } else {
            int j = word.charAt(index) - 'a';
            TrieNode temp = node.children[j];
            return temp != null && find(word, temp, index + 1);
        }
    }
}

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