tire树+dfs搜索

存储的单词都是小写字母，所以用tire树来存。

对于查询的单词来说：

• 如果遇到'.'，则枚举所有的存在的下一个字母进行搜索。
• 否则是单词，搜索下一个字母节点即可。

插入每个字符串：时间复杂度$O(N)$

查询每个字符串：最坏遍历所有的节点，时间复杂度$O(NM)$

空间复杂度$O(26N)$

class WordDictionary {
public:
    static const int N = 1e5 + 10;
    int son[N][26], idx;
    bool is_end[N];
    /** Initialize your data structure here. */

    WordDictionary() {
        idx = 0;
        memset(son, 0, sizeof son);
        memset(is_end, false, sizeof is_end);
    }

    void insert(string& word) {
        int p = 0;
        for (auto c : word) {
            int u = c - 'a';
            if (!son[p][u]) son[p][u] = ++ idx;
            p = son[p][u];
        }
        is_end[p] = true;
    }

    bool dfs(string& word, int k, int p) {
        if (k == word.size()) return is_end[p];//字符串枚举到最后了
        //不为.
        if (word[k] != '.') {
            if (son[p][word[k] - 'a']) return dfs(word, k + 1, son[p][word[k] - 'a']);
            return false;
        }
        //为.,枚举所有子节点
        for (int i = 0 ; i < 26 ; i ++) {
            if (son[p][i] && dfs(word, k + 1, son[p][i]))
                return true;
        }
        return false;    
    }


    void addWord(string word) {
        insert(word);
    }

    bool search(string word) {
        return dfs(word, 0, 0);
    }
};

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