C++實(shí)現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì))
[LeetCode] 211.Add and Search Word - Data structure design 添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
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.
LeetCode出新題的速度越來(lái)越快了,有點(diǎn)跟不上節(jié)奏的感覺(jué)了。這道題如果做過(guò)之前的那道 Implement Trie (Prefix Tree) 實(shí)現(xiàn)字典樹(shù)(前綴樹(shù))的話就沒(méi)有太大的難度了,還是要用到字典樹(shù)的結(jié)構(gòu),唯一不同的地方就是search的函數(shù)需要重新寫(xiě)一下,因?yàn)檫@道題里面'.'可以代替任意字符,所以一旦有了'.',就需要查找所有的子樹(shù),只要有一個(gè)返回true,整個(gè)search函數(shù)就返回true,典型的DFS的問(wèn)題,其他部分跟上一道實(shí)現(xiàn)字典樹(shù)沒(méi)有太大區(qū)別,代碼如下:
class WordDictionary { public: struct TrieNode { public: TrieNode *child[26]; bool isWord; TrieNode() : isWord(false) { for (auto &a : child) a = NULL; } }; WordDictionary() { root = new TrieNode(); } // Adds a word into the data structure. void addWord(string word) { TrieNode *p = root; for (auto &a : word) { int i = a - 'a'; if (!p->child[i]) p->child[i] = new TrieNode(); p = p->child[i]; } p->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) { return searchWord(word, root, 0); } bool searchWord(string &word, TrieNode *p, int i) { if (i == word.size()) return p->isWord; if (word[i] == '.') { for (auto &a : p->child) { if (a && searchWord(word, a, i + 1)) return true; } return false; } else { return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1); } } private: TrieNode *root; }; // Your WordDictionary object will be instantiated and called as such: // WordDictionary wordDictionary; // wordDictionary.addWord("word"); // wordDictionary.search("pattern");
討論:這道題有個(gè)很好的Follow up,就是當(dāng)搜索的單詞中存在星號(hào)怎么搞,星號(hào)的定義和Wildcard Matching中一樣,可以代表任意的字符串,包括空字符串,請(qǐng)參見(jiàn)評(píng)論區(qū)1樓。
類似題目:
參考資料:
https://leetcode.com/discuss/36246/my-java-trie-based-solution
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(211.添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)添加和查找單詞-數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)紙牌24點(diǎn)小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)紙牌24點(diǎn)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-10-10C++關(guān)于類結(jié)構(gòu)體大小和構(gòu)造順序,析構(gòu)順序的測(cè)試詳解
這篇文章主要介紹了C++類結(jié)構(gòu)體大小和構(gòu)造順序,析構(gòu)順序的測(cè)試,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-08-08C++中如何實(shí)現(xiàn)回調(diào)的方法示例
這篇文章主要給大家介紹了關(guān)于C++中如何實(shí)現(xiàn)回調(diào)的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用c++具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-10-10C 語(yǔ)言中strstr函數(shù)實(shí)例詳解
這篇文章主要介紹了C 語(yǔ)言中strstr函數(shù)實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07C++實(shí)現(xiàn)LeetCode(29.兩數(shù)相除)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(29.兩數(shù)相除),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C++中typedef 及其與struct的結(jié)合使用
這篇文章主要介紹了C++中typedef 及其與struct的結(jié)合使用,需要的朋友可以參考下2014-02-02C++ SOCKET多線程實(shí)現(xiàn)聊天小程序
這篇文章主要為大家詳細(xì)介紹了C++ SOCKET多線程實(shí)現(xiàn)聊天小程序,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06