題目：
設計一個資料結構來支持以下兩種操作：

• void addWord(word)：將字串 word 新增到資料結構中。
• bool search(word)：回傳某個字串是否存在於資料結構中，並且可以支援字串中的「.」任意符號，該任意符號可以對應任何一個字母。

範例：

WordDictionary wordDictionary = new WordDictionary();

wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");

wordDictionary.search("pad"); // 回傳 false
wordDictionary.search("bad"); // 回傳 true
wordDictionary.search(".ad"); // 回傳 true
wordDictionary.search("b.."); // 回傳 true

解題思路

要先有 #208. Implement Trie (Prefix Tree) 的基礎，addWord 一樣沒改變，search 先試著將原本的版本改成遞迴版本在加入「.」特殊處理，

實作：

class WordDictionary {
private:
    struct TrieNode {
        unordered_map<int, TrieNode*> children; // 子節點
        bool isEnd = false; // 是否為一個單詞的結尾
        
        TrieNode() {}
    };

    TrieNode* root;

public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for (auto c : word) {
            // 檢查有沒有存在，沒存在則建立
            if (!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;
    }

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

private:
    bool searchInNode(string& word, int i, TrieNode* node) {
        if (i == word.size()) {
            return node->isEnd;
        }

        char c = word[i];
        if (c == '.') {
            for (auto map : node->children) {
                if (searchInNode(word, i+1, map.second))
                    return true;
            }
            return false;
        }
        
        // 檢查有沒有存在，沒存在則 return false
        if (!node->children.count(c)) {
            return false;
        }
        node = node->children[c];
        return searchInNode(word, i+1, node);
    }
};

參考：
#211. Add and Search Word