leetcode 211. Add and Search Word - Data structure design-蒲公英云

leetcode 211. Add and Search Word - Data structure design

清疚 2022-07-27 13:34 232阅读 0赞

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

class TrieNode {
public:
    // Initialize your data structure here.
    bool isword;
    TrieNode*nxt[26];
    TrieNode() {
        for (int i = 0; i < 26; i++)
            nxt[i] = NULL;
        isword = false;
    }
};
class WordDictionary {
public:
    WordDictionary() {
        root = new TrieNode();
    }
    ~WordDictionary()
    {
        TrieNode*node = root;
        vector<TrieNode*>que, collect;
        que.push_back(root);
        while (!que.empty())
        {
            vector<TrieNode*>newque;
            for (int i = 0; i < que.size(); i++)
            {
                collect.push_back(que[i]);
                for (int j = 0; j < 26; j++)
                    if (que[i]->nxt[j] != NULL)
                        newque.push_back(que[i]->nxt[j]);
            }
            que = newque;
        }
        for (int i = 0; i < collect.size(); i++)
            delete collect[i];
    }
    // Adds a word into the data structure.
    void addWord(string word) {
        string s = word;
        TrieNode*node = root;
        for (int i = 0; i < s.length(); i++)
        {
            if (node->nxt[s[i] - 'a'] == NULL)
            {
                TrieNode*n = new TrieNode();
                node->nxt[s[i] - 'a'] = n;
            }
            node = node->nxt[s[i] - 'a'];
        }
        node->isword = true;
    }
    void do_once(vector<TrieNode*>&candi,string&s)
    {
        vector<TrieNode*>newcandi;
        for (int i = 0; i < candi.size(); i++)
        {
            if (s.front() == '.')
            {
                for (int j = 0; j < 26; j++)
                    if (candi[i]->nxt[j] != NULL)
                        newcandi.push_back(candi[i]->nxt[j]);
            }
            else
                if (candi[i]->nxt[s.front() - 'a'] != NULL)
                    newcandi.push_back(candi[i]->nxt[s.front() - 'a']);
        }
        s.erase(s.begin(), s.begin() + 1);
        candi = newcandi;
    }
    // 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) {
        string s = word;
        vector<TrieNode*>candi;
        candi.push_back(root);
        while (!s.empty() && !candi.empty())
            do_once(candi, s);
        if (s.empty() && !candi.empty())
        {
            for (int i = 0; i < candi.size(); i++)
                if (candi[i]->isword)
                    return true;
        }
        return false;
    }
private:
    TrieNode* root;
};
// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");