Let's make this one less mysterious. For 591. Tag Validator, the solution in this repository is mainly a stack 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: stack, backtracking, greedy.
The notes already sitting in the source point us in the right direction:
- Approach 1: Stack
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 isValidTagName, isValidCdata, isValid.
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//Approach 1: Stack
02//Runtime: 4 ms, faster than 58.93% of C++ online submissions for Tag Validator.
03//Memory Usage: 6.4 MB, less than 60.71% of C++ online submissions for Tag Validator.
04class Solution {
05public:
06 stack<string> stk;
07 bool containsTag;
08
09 bool isValidTagName(string s, bool ending){
10 if(s.size() < 1 || s.size() > 9)
11 return false;
12
13 for(int i = 0; i < s.size(); ++i){
14 if(s[i] < 'A' || s[i] > 'Z')
15 return false;
16 }
17
18 if(ending){
19 if(!stk.empty() && stk.top() == s){
20 //find the matching start tag
21 stk.pop();
22 }else{
23 //cannot find the matching start tag
24 return false;
25 }
26 }else{
27 //update containsTag when we find a start tag
28 containsTag = true;
29 stk.push(s);
30 }
31
32 return true;
33 };
34
35 bool isValidCdata(string s){
36 return s.find("[CDATA[") == 0;
37 };
38
39 bool isValid(string code) {
40 if(code[0] != '<' || code.back() != '>'){
41 return false;
42 }
43 //initialize, it is set when we find a valid start tag
44 containsTag = false;
45
46 for(int i = 0; i < code.size(); ++i){
47 bool ending = false;
48 int closeIndex;
49
50 if(containsTag && stk.empty()){
51 /*
52 if we have met a start tag,
53 the stack should contain its tag name
54 o.w. it means that the subsequent substring is
55 something outside that tag
56
57 e.g. "<A></A><B></B>"
58 */
59 return false;
60 }
61
62 if(code[i] == '<'){
63 if(!stk.empty() && code[i+1] == '!'){
64 //"<!]]>" is wrapped by a tag
65 closeIndex = code.find("]]>", i+1);
66 // cout << "potential cdata: " << code.substr(i+2, closeIndex-(i+2)) << endl;
67 if(closeIndex == string::npos ||
68 !isValidCdata(code.substr(i+2, closeIndex-(i+2)))){
69 return false;
70 }
71 }else{
72 if(code[i+1] == '/'){
73 ++i;
74 ending = true;
75 }
76 closeIndex = code.find('>', i+1);
77 // cout << "potential tagname: " << code.substr(i+1, closeIndex-(i+1)) << endl;
78 if(closeIndex < 0 ||
79 !isValidTagName(code.substr(i+1, closeIndex-(i+1)), ending)){
80 return false;
81 }
82 }
83 //next time start from a char behind cdata or tag's end
84 i = closeIndex;
85 }
86 }
87 return stk.empty() && containsTag;
88 }
89};
90
91//Approach 2: Regex, catastrophic backtracking
92//TLE
93//0 / 256 test cases passed.
94class Solution {
95public:
96 bool isValid(string code) {
97 /*
98 (1) <([A-Z]{1,9})>: outermost start-tag
99 all upper-case alphabets with length btw 1 to 9 inside <...>
100
101 (2) [^<]*: TAG_CONTENT except CDATA
102 all chars except '<' occurring 0 or more times
103
104 (3) (<\/?[A-Z]{1,9}>): start tag or end tag
105
106 (4) (<!\[CDATA\[(.*?)]]>): CDATA
107 matches any char within <!\[CDATA\[...]]>
108
109 (5) <\/1>: outermost end-tag
110 using "back-reference"
111 //https://www.regular-expressions.info/backref.html
112
113 (6) (.*?): match all chars until "]]>"
114 (inside (4)) using "non-greedy mode"
115 */
116 /*
117 this regex will lead to catastrophic backtracking
118 https://www.regular-expressions.info/catastrophic.html
119 */
120 regex pattern("<([A-Z]{1,9})>([^<]*((<\\/?[A-Z]{1,9}>)|(<!\\[CDATA\\[(.*?)]]>))?[^<]*)*<\/1>");
121 return regex_match(code, pattern);
122 }
123};
124
125//Approach 2: Regex
126//TLE
127//0 / 256 test cases passed.
128class Solution {
129public:
130 stack<string> stk;
131 bool containsTag;
132
133 bool isValidTagName(string s, bool ending){
134 if(ending){
135 if(!stk.empty() && stk.top() == s){
136 stk.pop();
137 }else{
138 return false;
139 }
140 }else{
141 containsTag = true;
142 stk.push(s);
143 }
144
145 return true;
146 };
147
148 bool isValid(string code) {
149 regex pattern("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*");
150 // cout << "matching regex" << endl;
151 if(!regex_match(code, pattern))
152 return false;
153 // cout << "matched regex" << endl;
154
155 //initialize, it is set when we find a valid start tag
156 containsTag = false;
157
158 for(int i = 0; i < code.size(); ++i){
159 bool ending = false;
160
161 if(containsTag && stk.empty()){
162 return false;
163 }
164
165 if(code[i] == '<'){
166 if(code[i+1] == '!'){
167 //"<!]]>" is wrapped by a tag
168 i = code.find("]]>", i+1);
169 continue;
170 }
171
172 if(code[i+1] == '/'){
173 ++i;
174 ending = true;
175 }
176 int closeIndex = code.find('>', i+1);
177 // cout << "potential tagname: " << code.substr(i+1, closeIndex-(i+1)) << endl;
178 if(closeIndex < 0 ||
179 !isValidTagName(code.substr(i+1, closeIndex-(i+1)), ending)){
180 return false;
181 }
182 //next time start from a char behind cdata or tag's end
183 i = closeIndex;
184 }
185 }
186 return stk.empty() && containsTag;
187 }
188};
189
190//regex, replace
191//https://leetcode.com/problems/tag-validator/discuss/103370/short-python-accepted-but-not-sure-if-correct
192//Runtime: 168 ms, faster than 7.14% of C++ online submissions for Tag Validator.
193//Memory Usage: 29.2 MB, less than 7.14% of C++ online submissions for Tag Validator.
194class Solution {
195public:
196 bool isValid(string code) {
197 if(code == "t") return false;
198
199 // cout << code << endl;
200 /*
201 in C++, \\ will be interpreted as \
202 in regex, \[ will be interpreted as the char '[',
203 different from the [] when we need to matches any single character in brackets.
204 */
205 regex pattern("<!\\[CDATA\\[.*?\\]\\]>");
206
207 code = regex_replace(code, pattern, "c");
208 // cout << code << endl;
209
210 string prev = "";
211 pattern = regex("<([A-Z]{1,9})>[^<]*</\\1>");
212
213 while(code != prev){
214 prev = code;
215 code = regex_replace(code, pattern, "t");
216 // cout << code << endl;
217 }
218
219 return code == "t";
220 }
221};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.