211. Add and Search Word - Data structure design
and Data word add search Design Structure
2023-09-11 14:22:45 时间
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.
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
.
Approach #1: Trie. [C++]
class TrieNode { public: TrieNode* children[26]; bool word; TrieNode() { word = false; memset(children, NULL, sizeof(children)); } }; class WordDictionary { public: /** Initialize your data structure here. */ WordDictionary() { root = new TrieNode(); } /** Adds a word into the data structure. */ void addWord(string word) { TrieNode* node = root; for (char c : word) { if (!node->children[c-'a']) node->children[c-'a'] = new TrieNode(); node = node->children[c-'a']; } node->word = 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 query(word.c_str(), root); } private: TrieNode* root; bool query(const char* word, TrieNode* node) { for (int i = 0; word[i] && node; ++i) { if (word[i] != '.') { node = node->children[word[i] - 'a']; } else { TrieNode* temp = node; for (int j = 0; j < 26; ++j) { node = temp->children[j]; if (query(word+i+1, node)) { return true; } } } } return node && node->word; } }; /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * bool param_2 = obj.search(word); */
Analysis:
这一题用到了一个叫做Trie的数据结构,虽然说以前学过但是当时自己也就是看一遍也没有真正的运用这种数据结构做过题。所以一开始看到这道题时完全没有思路,后来看了别人的题解。比较好奇的是如果将35行中的const关键字省略的话回编译出错,现在还不知道为什么会这样。虽然最近一直再看关于C++的书籍,但是看过书之后还是感觉对C++一点都不了解。
相关文章
- NetBouncer: Active Device and Link Failure Localization in Data Center Networks [技术学习]
- 大咖云集!Kubernetes and Cloud Native Meetup 深圳站开始报名!
- [XState] Drag and Drop example (data-state, attr in css)
- [Spring Boot] Adding JPA and Spring Data JPA
- [GraphQL] Query Local and Remote Data in Apollo Link State
- [GraphQL] Fetch Server Data and Client-side State in One Query using React Apollo + GraphQL
- [Python] Read and plot data from csv file
- [Nuxt] Load Data from APIs with Nuxt and Vuex
- [Ramda] Pick and Omit Properties from Objects Using Ramda
- [Angular2 Form] Nested formGroup, and usage of formGroupName
- [Hapi.js] POST and PUT request payloads
- Java Method Logging with AOP and Annotations
- [React Testing] Use Generated Data in Tests with tests-data-bot to Improve Test Maintainability
- [GraphQL] Fetch Server Data and Client-side State in One Query using React Apollo + GraphQL
- [Nuxt] Add Arrays of Data to the Vuex Store and Display Them in Vue.js Templates
- [RxJS] Creation operators: interval and timer
- between...and..
- SAP CRM WebClient UI Report transaction data request and response
- Atitit.atiRI 与 远程调用的理论and 设计
- 【codeforces 812A】Sagheer and Crossroads
- SAP Fiori Elements - fixed value help data request and how drop down list entry is rendered
- 成功解决TypeError: Cannot compare types ‘ndarray(dtype=float64)‘ and ‘str‘
- *args and **kwargs in Python 变长参数
- Android12安装报错:Targeting S+ (version 31 and above) requires that an explicit value for android:export
- Data Mining and Machine Learning in Cybersecurity PDF
- 论文阅读《Named Entity Recognition with Small Strongly Labeled and Large Weakly Labeled Data》
- Ambiguous method call. Both findViewById (int) in AppCompatActivity and findViewById (int) in Activi