2022-9-18 Leetcode211.211. 添加与搜索单词 - 数据结构设计【前缀树】

使用vector比较好，使用map会造成超时。

struct Node {
    bool isWord;
    vector<Node*> next;
    Node():isWord(false) {next.assign(26, nullptr);}
    ~Node(){
        for (auto c : next) {
            delete c;
        }
    }
};
class WordDictionary {
private:
    Node* root;
    bool match(Node *cur, string word, int index) {
        if (index == word.size())
            return cur->isWord;

        char ch = word[index];
        if (ch != '.') {
            int i = ch - 'a';
            if (cur->next[i] == nullptr)
                return false;
            return match(cur->next[i], word, index + 1);
        } else {
            for (int i = 0; i < 26; i++) {
                if (cur->next[i] != nullptr) {
                    if (match(cur->next[i], word, index + 1))
                        return true;
                }
            }
            return false;
        }
    }
public:
    WordDictionary() {
        root = new Node();
    }
    
    void addWord(string word) {
        Node* cur = root;
        for (auto & ch: word) {
            int i = ch - 'a';
            if (cur->next[i] == nullptr) {
                cur->next[i] = new Node();
            }
            cur = cur->next[i];
        }
        if (cur->isWord == false) {
            cur->isWord = true;
        }
    }
    
    bool search(string word) {
        return match(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);
 */