211. 添加与搜索单词 - 数据结构设计

来自最快速度的示例代码

取消同步用的（后面的字符串插入可能很多，输入很多）：

static const auto acc = []() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return nullptr;
}();

和 208.实现 Trie (前缀树)的区别主要是，遇到.需要对所有的child结点深搜，所以多加了一个dfs用的函数。

class WordDictionary {
  public:
    struct TrieNode {
      public:
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for (auto &a : child)
                a = NULL;
        }
    };

    WordDictionary() { root = new TrieNode(); }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *p = root;
        for (auto &a : word) {
            int i = a - 'a';
            if (!p->child[i])
                p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }

    // 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); }

    bool dfs(string &word, TrieNode *p, int i) {
        if (i == word.size())
            return p->isWord;
        // 如果是.全部child结点都搜
        if (word[i] == '.') {
            for (auto &a : p->child) {
                if (a && dfs(word, a, i + 1))
                    return true;
            }
            return false;
            // 如果不是.挑那一个搜
        } else {
            return p->child[word[i] - 'a'] &&
                   dfs(word, p->child[word[i] - 'a'], i + 1);
        }
    }

  private:
    TrieNode *root;
};