Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary()Initializes the object.void addWord(word)Addswordto the data structure, it can be matched later.bool search(word)Returnstrueif there is any string in the data structure that matcheswordorfalseotherwise.wordmay contain dots'.'where dots can be matched with any letter.
Example:
Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
Constraints:
1 <= word.length <= 500wordinaddWordconsists lower-case English letters.wordinsearchconsist of'.'or lower-case English letters.- At most
50000calls will be made toaddWordandsearch.
Solution: Hashtables
The first hashtable stores all the words, if there is no dot in the search pattern. Do a full match.
There are also per length hashtable to store words of length k. And do a brute force match.
Time complexity: Init: O(n*l)
search: best: O(l) worst: O(n*l)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua class WordDictionary { public: // Adds a word into the data structure. void addWord(string word) { words.insert(word); ws[word.length()].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) { if (word.find(".") == string::npos) return words.count(word); for (const string& w : ws[word.length()]) if (match(word, w)) return true; return false; } bool match(const string& p, const string& w) { for (int i = 0; i < p.length(); ++i) { if (p[i] == '.') continue; if (p[i] != w[i]) return false; } return true; } private: unordered_set<string> words; unordered_map<int, unordered_set<string>> ws; }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment