题目
标签验证器
思路
如果当前字符为 <，需要考虑下面四种情况：
- 如果下一个字符为 /，那么说明我们遇到了一个结束标签。我们需要定位下一个 > 的位置 j，此时
code[i+2..j−1] 就是该结束标签的名称。我们需要判断该名称与当前栈顶的名称是否匹配，如果匹配，说明名称的标签已经闭合，我们需要将当前栈顶的名称弹出。同时根据规则 1，我们需要保证整个 code 被闭合标签包围，因此如果栈中已经没有标签，但是 j 并不是 code 的末尾，那么说明后续还会有字符，它们不被闭合标签包围。
- 如果下一个字符为 !，那么说明我们遇到了一个 cdata，我们需要继续往后读 77 个字符，判断其是否为 \texttt{[CDATA[}[CDATA[。在这之后，我们定位下一个 ]]> 的位置 j，此时
code[i+9..j−1] 就是 cdata 中的内容，它不需要被解析，所以我们也不必进行任何验证。需要注意的是，根据规则 1，栈中需要存在至少一个开放的标签。
- 如果下一个字符为大写字母，那么说明我们遇到了一个开始标签。我们需要定位下一个 > 的位置 j，此时
code[i+2..j−1] 就是该开始标签的名称。我们需要判断该名称是否恰好由 1 至 9 个大写字母组成，如果是，说明该标签合法，我们需要将该名称放入栈顶。
- 除此之外，如果不存在下一个字符，或者下一个字符不属于上述三种情况，那么 code 是不合法的。
如果当前的字符为其它字符，那么根据规则 1，栈中需要存在至少一个开放的标签。
在遍历完成后，我们还需要保证此时栈中没有任何（还没有结束的）标签。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
bool isValid(string code) {
stack<string> stk;
int i = 0, n = code.size();
while(i < n){
if(code[i] == '<'){
if(i == n - 1) return false;
else if(code[i + 1] >= 'A' && code[i + 1] <= 'Z'){
int j = code.find('>', i);
if(j == string::npos) return false;
string str = code.substr(i + 1, j - i - 1);
if(str.length() < 1 || str.length() > 9) return false;
for(int k = 0; k < str.size(); k ++){
if(str[k] < 'A' || str[k] > 'Z')
return false;
}
stk.push(str);
i = j + 1;
}
else if(code[i + 1] == '/'){
int j = code.find('>', i);
if(j == string::npos) return false;
string str = code.substr(i + 2, j - i - 2);
if(stk.empty() || stk.top() != str) return false;
stk.pop();
i = j + 1;
if(stk.empty() && i != n) return false;
}
else if(code[i + 1] == '!'){
if(stk.empty()) return false;
string str = code.substr(i + 2, 7);
if(str != "[CDATA[") return false;
int j = code.find("]]>", i);
if(j == string::npos) return false;
i = j + 1;
}
else return false;
}
else{
if(stk.empty()) return false;
i++;
}
}
return stk.empty();
}
};
|
- 时间复杂度：O(n)，其中 n 为 code 的长度，我们只需要对 code 进行一次遍历。
- 空间复杂度：O(n)，即为栈存储标签名称需要使用的空间。
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.3 MB, 在所有 C++ 提交中击败了96.00%的用户
通过测试用例：260 / 260