c.cpp

class WordDictionary {
private:
    struct Node {
        bool isWord;
        vector<Node*>sub;
        Node(): isWord(false), sub(vector<Node*>(26, NULL)){}
    };
    Node *dict = new Node();
public:
    
    // Adds a word into the data structure.
    void addWord(string word) {
        Node *cur = dict;
        for (int i = 0; i < word.size(); i++) {
            int k = word[i] - 'a';
            if (cur -> sub[k] == NULL) cur -> sub[k] = new Node();
            cur = cur -> sub[k];
        }
        cur -> 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) {
        queue<Node*>curNodes;
        curNodes.push(dict);
        for (int i = 0; i < word.size() && !curNodes.empty(); i++) {
            for (int k = (int)curNodes.size() - 1; k >= 0 && !curNodes.empty(); k--) {
                Node *cur = curNodes.front();
                if (word[i] == '.') {
                    for (int m = 0; m < 26; m++) {
                        if (cur -> sub[m] != NULL) curNodes.push(cur -> sub[m]);
                    }
                } else if (cur -> sub[word[i] - 'a'] != NULL){
                    curNodes.push(cur -> sub[word[i] - 'a']);
                }
                curNodes.pop();
            }
        }
        for (int i = (int)curNodes.size() - 1; i >= 0; i--) {
            if (curNodes.front() -> isWord) return true;
            curNodes.pop();
        }
        return false;
    }
};