LeetCode/solutions/211. Add and Search Word - Data structure design.md

# [211. Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/)

# 思路

 这题其实就是[208. Implement Trie(Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/)的升级版，会做208题此题就没啥问题了。
 不同的地方就是查询时`.`可以代替任意字符，所以一旦有了`.`，就需要查找所有的子树，典型的DFS的问题。
 
 # C++
 ```C++
class TrieNode{
public:
    bool isLeaf;
    vector<TrieNode *>nexts = vector<TrieNode *>(26, NULL);
    TrieNode(bool _isLeaf){
        isLeaf = _isLeaf;
    } 
};

class WordDictionary {
private:
    TrieNode *root = new TrieNode(false);
public:
    /** Initialize your data structure here. */
    WordDictionary() {}
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode *p = root;
        for(char c: word){
            if(p -> nexts[c-'a'] == NULL){
                TrieNode *node = new TrieNode(false);
                p -> nexts[c-'a'] = node;
                p = node;
            }
            else p = p -> nexts[c-'a'];
        }
        p -> isLeaf = true;
    }
    
    bool DFS(const string &word, TrieNode *node, int start){
        if(start == word.size()) return node -> isLeaf;
        
        if(word[start] == '.'){
            for(TrieNode *p: node -> nexts)
                if(p != NULL && DFS(word, p, start+1)) return true;
            return false;
        }
        
        TrieNode *p = node -> nexts[word[start] - 'a'];
        if(!p) return false;
        return DFS(word, p, start + 1);
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return DFS(word, root, 0);
    }
};
 ```