前缀树

注意当字符为.的时候需要用深度优先搜索分别判断每个子节点是否为空，只要有非空子节点即OK

class Trie {
public:
    vector<Trie*> children;
    bool isEnd;
    Trie() : children(26), isEnd(false) {}
    void insert(const string &word) {
        Trie* node = this;
        for (char ch : word) {
            if(node->children[ch-'a'] == nullptr) {
                node->children[ch-'a'] = new Trie();
            }
            node = node->children[ch-'a'];
        }
        node->isEnd = true;
    }

};

class WordDictionary {
    Trie* root;
public:
    WordDictionary() {
        root = new Trie();
    }
    
    void addWord(string word) {
        root->insert(word);
    }
    
    bool search(string word) {
        return dfs(0, word, root);
    }

    bool dfs(int index, string &word, Trie* node) {
        if (index == word.size()) {
            return node->isEnd;
        }
        char ch = word[index];
        if (ch >= 'a' && ch <= 'z') {
            Trie* child = node->children[ch-'a'];
            return child != nullptr && dfs(index+1, word, child);
        }else if(ch == '.') {
            for (int i = 0; i < 26; i++) {
                Trie* child = node->children[i];
                // 注意与这种写法的区别：return child != nullptr && dfs(index+1, word, child);
                if(child != nullptr && dfs(index+1, word, child)) return true;
            }
        }
        return false;
    }
};

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