Let's make this one less mysterious. For 211. Add and Search Word - Data structure design, the solution in this repository is mainly a data structure design solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design, trie, stack, prefix sums.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are containsKey, put, setEnd, getEnd, insert.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 132 ms, faster than 50.37% of C++ online submissions for Add and Search Word - Data structure design.
02//Memory Usage: 62.8 MB, less than 35.19% of C++ online submissions for Add and Search Word - Data structure design.
03
04class TrieNode{
05private:
06 vector<TrieNode*> links;
07 int R = 26;
08 bool isEnd = false;
09public:
10 TrieNode() {
11 links = vector<TrieNode*>(R);
12 }
13
14 bool containsKey(char c){
15 return links[c-'a']!=NULL;
16 }
17
18 TrieNode* get(char c){
19 return links[c-'a'];
20 }
21
22 void put(char c, TrieNode* node){
23 links[c-'a'] = node;
24 }
25
26 void setEnd(){
27 isEnd = true;
28 }
29
30 bool getEnd(){
31 return isEnd;
32 }
33};
34
35struct TrieNodeDepth{
36 TrieNode* node = NULL;
37 int depth = 0;
38
39 TrieNodeDepth(){
40 }
41
42 TrieNodeDepth(TrieNode* n, int d){
43 node = n;
44 depth = d;
45 }
46};
47
48class Trie{
49private:
50 TrieNode* root;
51 int R = 26;
52
53 TrieNode* searchPrefix(string word, TrieNode* node = NULL){
54 //the default value of argument should be a const, not a variable
55 //, so we set node = NULL in function's argument list
56 //, and then set it to root later
57 if(node == NULL) node = root;
58 //fail to search all branches when c == '.'
59 /**
60 for(int i = 0; i < word.size(); i++){
61 char c = word[i];
62 if(c == '.'){
63 for(int j = 0; j < R; j++){
64 if(node->containsKey('a'+j)){
65 TrieNode* subnode = searchPrefix(word.substr(j, word.size()), node->get('a'+j));
66 cout << "subnode" << i << " " << (char)('a'+j) << " " << (subnode != NULL) << endl;
67 if(subnode != NULL){
68 cout << "subnode is end: " << subnode->getEnd() << endl;
69 return subnode;
70 }
71 }
72 }
73 }else if(node->containsKey(c)){
74 node = node->get(c);
75 }else{
76 return NULL;
77 }
78 }
79 **/
80 //should be initialized as NULL, if later we find better node, we update it
81 TrieNode* ans = NULL;
82 stack<TrieNodeDepth> stk;
83 stk.push(TrieNodeDepth(node, 0));
84 while(!stk.empty()){
85 TrieNodeDepth tnd = stk.top();
86 stk.pop();
87 TrieNode* node = tnd.node;
88 int depth = tnd.depth;
89 if(depth == word.size()){
90 if(node != NULL && node->getEnd()){
91 // cout << "return end node" << endl;
92 ans = node;
93 //this is the best kind of node, break so that ans won't be updated anymore
94 break;
95 }else if(node != NULL){
96 // cout << "not null node" << endl;
97 ans = node;
98 //continue to see if there is better node
99 continue; //don't need to push children anymore
100 }
101 }
102 char c = word[depth];
103 // cout << depth << " " << c << endl;
104 if(c == '.'){
105 //push all branches into stack
106 for(int j = 0; j < R; j++){
107 char tmpc = 'a'+j;
108 if(node->containsKey(tmpc)){
109 stk.push(TrieNodeDepth(node->get(tmpc), depth+1));
110 }
111 }
112 }else if(node->containsKey(c)){
113 stk.push(TrieNodeDepth(node->get(c), depth+1));
114 }
115 //cannot early return, because there could be better nodes still in the stack
116 // else{
117 // return NULL;
118 // }
119 }
120 return ans;
121 }
122
123public:
124 Trie(){
125 root = new TrieNode();
126 }
127
128 void insert(string word){
129 TrieNode* node = root;
130 for(char c : word){
131 if(!node->containsKey(c)){
132 node->put(c, new TrieNode());
133 }
134 node = node->get(c);
135 }
136 node->setEnd();
137 }
138
139 bool search(string word){
140 TrieNode* node = searchPrefix(word);
141 // cout << "search: " << (node != NULL) << endl;
142 // if(node != NULL) cout << "search, is end: " << (node->getEnd()) << endl;
143 return node != NULL && node->getEnd();
144 }
145
146 bool startsWith(string prefix){
147 TrieNode* node = searchPrefix(prefix);
148 return node != NULL;
149 }
150};
151
152class WordDictionary {
153public:
154 Trie* trie;
155
156 /** Initialize your data structure here. */
157 WordDictionary() {
158 trie = new Trie();
159 }
160
161 /** Adds a word into the data structure. */
162 void addWord(string word) {
163 trie->insert(word);
164 }
165
166 /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
167 bool search(string word) {
168 return trie->search(word);
169 }
170};
171
172/**
173 * Your WordDictionary object will be instantiated and called as such:
174 * WordDictionary* obj = new WordDictionary();
175 * obj->addWord(word);
176 * bool param_2 = obj->search(word);
177 */
178
179//solution from discussion
180//https://leetcode.com/problems/add-and-search-word-data-structure-design/discuss/59554/My-simple-and-clean-Java-code
181//Runtime: 192 ms, faster than 22.70% of C++ online submissions for Add and Search Word - Data structure design.
182//Memory Usage: 111.5 MB, less than 6.70% of C++ online submissions for Add and Search Word - Data structure design.
183
184class TrieNode{
185public:
186 vector<TrieNode*> links;
187 string item;
188
189 TrieNode(){
190 links = vector<TrieNode*>(26);
191 item = "";
192 }
193};
194
195class WordDictionary {
196public:
197 TrieNode* root = new TrieNode();
198
199 /** Initialize your data structure here. */
200 WordDictionary() {
201 }
202
203 /** Adds a word into the data structure. */
204 void addWord(string word) {
205 TrieNode* node = root;
206 for(char c : word){
207 if(node->links[c-'a'] == NULL){
208 node->links[c-'a'] = new TrieNode();
209 }
210 node = node->links[c-'a'];
211 }
212 //mark it as end
213 node->item = word;
214 }
215
216 bool match(string word, int depth, TrieNode* node){
217 //node->item != "" means the node is end
218 if(depth == word.size()) return (node->item != "");
219 char c = word[depth];
220 // cout << depth << " " << c << endl;
221 if(c != '.'){
222 //recursive search
223 return (node->links[c-'a'] != NULL) && match(word, depth+1, node->links[c-'a']);
224 }else{
225 //search for all its children
226 for(int i = 0; i < node->links.size(); i++){
227 if(node->links[i] != NULL){
228 if(match(word, depth+1, node->links[i])){
229 return true;
230 }
231 }
232 }
233 }
234 return false;
235 }
236
237 /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
238 bool search(string word) {
239 return match(word, 0, root);
240 }
241};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.