leetcode 211. Add and Search Word - Data structure design

清疚 2022-07-27 13:34 159阅读 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");

accepted