Add and Search Word

原题地址：https://leetcode.com/problems/add-and-search-word-data-structure-design/#/description

题目：

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.

解题思路：
这道题主要是要理解TrieNode里面主要存了什么（isLeaf 和children node）。然后就是注意root是空的，第一个char是从根的children开始。


代码：

class TrieNode{
    boolean isLeaf;
    TrieNode[] children = new TrieNode[26];
}
TrieNode root = new TrieNode();
public void addWord(String word) {
    TrieNode curr = root;
    for(int i = 0; i <= word.length() -1; i++){
        char c = word.charAt(i);
        if(curr.children[c - 'a'] != null){
            curr = curr.children[c - 'a'];
        }
        else{
            TrieNode temp = new TrieNode();
            curr.children[c - 'a'] = temp;
            curr = curr.children[c - 'a'];
        }
    }
    curr.isLeaf = true;
}
public boolean search(String word) {
    TrieNode curr = root;
    for(int i = 0; i <= word.length() - 1; i++){
        char c = word.charAt(i);
        if(c == '.'){
            return dfs(curr, i, word);
        }
        else{
            if(curr.children[c - 'a'] == null){
                return false;
            }
            else{
                curr = curr.children[c - 'a'];
            }
        }
    }
    return curr.isLeaf;
}
private boolean dfs(TrieNode curr, int pos, String word){
    if(pos == word.length()){
        return curr.isLeaf;
    }
    char c = word.charAt(pos);
    if(c == '.'){
        for(int j = 0; j <= 25; j++){
            if(curr.children[j] != null && dfs(curr.children[j], pos + 1, word)){
                return true;
            }
        }
    }
    else if(curr.children[c - 'a'] != null){
        return dfs(curr.children[c - 'a'], pos + 1, word);
    }
    return false;
}