C++實現LeetCode(211.添加和查找單詞-數據結構設計)
[LeetCode] 211.Add and Search Word – Data structure design 添加和查找單詞-數據結構設計
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.
LeetCode出新題的速度越來越快瞭,有點跟不上節奏的感覺瞭。這道題如果做過之前的那道 Implement Trie (Prefix Tree) 實現字典樹(前綴樹)的話就沒有太大的難度瞭,還是要用到字典樹的結構,唯一不同的地方就是search的函數需要重新寫一下,因為這道題裡面’.’可以代替任意字符,所以一旦有瞭’.’,就需要查找所有的子樹,隻要有一個返回true,整個search函數就返回true,典型的DFS的問題,其他部分跟上一道實現字典樹沒有太大區別,代碼如下:
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");
討論:這道題有個很好的Follow up,就是當搜索的單詞中存在星號怎麼搞,星號的定義和Wildcard Matching中一樣,可以代表任意的字符串,包括空字符串,請參見評論區1樓。
類似題目:
Implement Trie (Prefix Tree)
Wildcard Matching
參考資料:
https://leetcode.com/discuss/36246/my-java-trie-based-solution
到此這篇關於C++實現LeetCode(211.添加和查找單詞-數據結構設計)的文章就介紹到這瞭,更多相關C++實現添加和查找單詞-數據結構設計內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(648.替換單詞)
- C++實現LeetCode(676.實現神奇字典)
- Go 語言前綴樹實現敏感詞檢測
- 基於Python實現西西成語接龍小助手
- C++實現LeetCode(110.平衡二叉樹)