您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C++實(shí)現(xiàn)LeetCode之添加和查找單詞的示例分析,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
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.
click to show hint.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
LeetCode出新題的速度越來越快了,有點(diǎn)跟不上節(jié)奏的感覺了。這道題如果做過之前的那道 Implement Trie (Prefix Tree) 實(shí)現(xiàn)字典樹(前綴樹)的話就沒有太大的難度了,還是要用到字典樹的結(jié)構(gòu),唯一不同的地方就是search的函數(shù)需要重新寫一下,因?yàn)檫@道題里面'.'可以代替任意字符,所以一旦有了'.',就需要查找所有的子樹,只要有一個(gè)返回true,整個(gè)search函數(shù)就返回true,典型的DFS的問題,其他部分跟上一道實(shí)現(xiàn)字典樹沒有太大區(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");
關(guān)于“C++實(shí)現(xiàn)LeetCode之添加和查找單詞的示例分析”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯(cuò),請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。