This is one of those problems where the clean idea matters more than the amount of code. For 1032. Stream of Characters, the solution in this repository is mainly a trie solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: trie.
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 add, query, reverse_add.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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: 1760 ms, faster than 6.41% of C++ online submissions for Stream of Characters.
02//Memory Usage: 105.9 MB, less than 58.81% of C++ online submissions for Stream of Characters.
03class TrieNode{
04public:
05 vector<TrieNode*> children;
06 bool isEnd;
07
08 TrieNode(){
09 children = vector<TrieNode*>(26, nullptr);
10 isEnd = false;
11 }
12};
13
14class StreamChecker {
15public:
16 TrieNode* root;
17 int max_word_len;
18 vector<TrieNode*> nodes;
19
20 void add(string& word){
21 TrieNode* cur = root;
22
23 for(char& c : word){
24 if(cur->children[c-'a'] == nullptr){
25 cur->children[c-'a'] = new TrieNode();
26 }
27 cur = cur->children[c-'a'];
28 }
29
30 cur->isEnd = true;
31 }
32
33 StreamChecker(vector<string>& words) {
34 root = new TrieNode();
35 max_word_len = 0;
36
37 for(string& word : words){
38 add(word);
39 max_word_len = max(max_word_len, (int)word.size());
40 }
41 }
42
43 bool query(char letter) {
44 bool found = false;
45
46 nodes.push_back(root);
47 // cout << "nodes: " << nodes.size() << endl;
48 for(int i = nodes.size()-1; i >= 0; --i){
49 // cout << "i: " << i << " ";
50 if(nodes[i]->children[letter-'a'] == nullptr){
51 nodes.erase(nodes.begin()+i);
52 }else{
53 nodes[i] = nodes[i]->children[letter-'a'];
54 if(nodes[i]->isEnd){
55 found = true;
56 }
57 }
58 }
59
60 return found;
61 }
62};
63
64/**
65 * Your StreamChecker object will be instantiated and called as such:
66 * StreamChecker* obj = new StreamChecker(words);
67 * bool param_1 = obj->query(letter);
68 */
69
70//revised from above, add restriction of the level of pointers, but slower than above
71//Runtime: 1928 ms, faster than 5.12% of C++ online submissions for Stream of Characters.
72//Memory Usage: 105.7 MB, less than 66.34% of C++ online submissions for Stream of Characters.
73class TrieNode{
74public:
75 vector<TrieNode*> children;
76 bool isEnd;
77 int level;
78
79 TrieNode(){
80 children = vector<TrieNode*>(26, nullptr);
81 isEnd = false;
82 level = 0;
83 }
84};
85
86class StreamChecker {
87public:
88 TrieNode* root;
89 int max_word_len;
90 vector<TrieNode*> nodes;
91
92 void add(string& word){
93 TrieNode* cur = root;
94
95 for(char& c : word){
96 if(cur->children[c-'a'] == nullptr){
97 cur->children[c-'a'] = new TrieNode();
98 cur->children[c-'a']->level = cur->level+1;
99 }
100 cur = cur->children[c-'a'];
101 }
102
103 cur->isEnd = true;
104 }
105
106 StreamChecker(vector<string>& words) {
107 root = new TrieNode();
108 max_word_len = 0;
109
110 for(string& word : words){
111 add(word);
112 max_word_len = max(max_word_len, (int)word.size());
113 }
114 }
115
116 bool query(char letter) {
117 bool found = false;
118
119 nodes.push_back(root);
120 // cout << "nodes: " << nodes.size() << endl;
121 for(int i = nodes.size()-1; i >= 0; --i){
122 // cout << "i: " << i << " ";
123 if(nodes[i]->children[letter-'a'] == nullptr ||
124 nodes[i]->level > max_word_len){
125 nodes.erase(nodes.begin()+i);
126 }else{
127 nodes[i] = nodes[i]->children[letter-'a'];
128 if(nodes[i]->isEnd){
129 found = true;
130 }
131 }
132 }
133
134 return found;
135 }
136};
137
138/**
139 * Your StreamChecker object will be instantiated and called as such:
140 * StreamChecker* obj = new StreamChecker(words);
141 * bool param_1 = obj->query(letter);
142 */
143
144//store words in reverse order, and find the query string in reverse order
145//also pruning when query string is too long
146//https://leetcode.com/problems/stream-of-characters/discuss/278769/Java-Trie-Solution
147//Runtime: 624 ms, faster than 59.45% of C++ online submissions for Stream of Characters.
148//Memory Usage: 265.8 MB, less than 13.61% of C++ online submissions for Stream of Characters.
149class TrieNode{
150public:
151 vector<TrieNode*> children;
152 bool isEnd;
153
154 TrieNode(){
155 children = vector<TrieNode*>(26, nullptr);
156 isEnd = false;
157 }
158};
159
160class StreamChecker {
161public:
162 TrieNode* root;
163 int max_word_len;
164 string past;
165
166 void reverse_add(string& word){
167 TrieNode* cur = root;
168
169 for(int i = word.size()-1; i >= 0; --i){
170 char c = word[i];
171 if(cur->children[c-'a'] == nullptr){
172 cur->children[c-'a'] = new TrieNode();
173 }
174 cur = cur->children[c-'a'];
175 }
176
177 cur->isEnd = true;
178 }
179
180 StreamChecker(vector<string>& words) {
181 root = new TrieNode();
182 max_word_len = 0;
183
184 for(string& word : words){
185 reverse_add(word);
186 max_word_len = max(max_word_len, (int)word.size());
187 }
188 }
189
190 bool query(char letter) {
191 past = letter + past;
192 //this avoids TLE!!
193 if(past.size() > max_word_len){
194 past = past.substr(0, max_word_len);
195 }
196 TrieNode* cur = root;
197
198 for(char& c : past){
199 cur = cur->children[c-'a'];
200 if(!cur) break;
201 if(cur->isEnd){
202 return true;
203 }
204 }
205
206 return false;
207 }
208};
209
210/**
211 * Your StreamChecker object will be instantiated and called as such:
212 * StreamChecker* obj = new StreamChecker(words);
213 * bool param_1 = obj->query(letter);
214 */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.