211.添加与搜索单词 (Medium)*

class TrieNode {
public:
    bool isEnd;
    vector<TrieNode*> next;
    TrieNode() : isEnd(false), next(vector<TrieNode*>(26, nullptr)) {}
};
class WordDictionary {
private:
    TrieNode* root;
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        auto cur = root;
        for(auto& c : word) {
            if(cur->next[c - 'a'] == nullptr) {
                cur->next[c - 'a'] = new TrieNode();
            }
            cur = cur->next[c - 'a'];
        }
        cur->isEnd = true;
    }

    bool dfs(TrieNode* cur, string& word, int pos) {
        if(cur == nullptr) {
            return false;
        }
        if(pos >= word.length()) {
            return cur->isEnd;
        }
        if(word[pos] == '.') {
            for(auto p : cur->next) {
                if(p != nullptr && dfs(p, word, pos + 1)) {
                    return true;
                }
            }
        }else {
            if(cur->next[word[pos] - 'a'] != nullptr && dfs(cur->next[word[pos] - 'a'], word, pos + 1)) {
                return true;
            }
        }
        return false;
    }

    /** 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(root, word, 0);
    }
};

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

class WordDictionary {
private:
    unordered_map<int, unordered_set<string>> words;
public:
    /** Initialize your data structure here. */
    WordDictionary() { }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        int len = word.length();
        words[len].insert(word);
    }

    /** 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) {
        int len = word.length();
        if(words.count(len) != 0) {
            bool found = false;
            for(auto& s : words[len]) {
                found = true;
                for(int i = 0; i < len; i++) {
                    if(!(word[i] == '.' || word[i] == s[i])) {
                        found = false;
                        break;
                    }
                }
                if(found) {
                    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);
 */