Hard
题目描述
给定一个表示代码片段的字符串，实现一个标签验证器来解析代码并返回它是否有效。
如果代码片段满足以下所有规则，则它是有效的：
- 代码必须包装在有效的闭合标签中。否则，代码无效。
- 闭合标签（不一定有效）具有以下格式：
<TAG_NAME>TAG_CONTENT</TAG_NAME>。其中，<TAG_NAME>是开始标签，</TAG_NAME>是结束标签。开始和结束标签中的 TAG_NAME 应该相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都有效时，闭合标签才有效。 - 有效的 TAG_NAME 只包含大写字母，长度在 [1,9] 范围内。否则，TAG_NAME 无效。
- 有效的 TAG_CONTENT 可能包含其他有效的闭合标签、cdata 和任何字符，除了不匹配的
<、不匹配的开始和结束标签以及具有无效 TAG_NAME 的不匹配或闭合标签。否则，TAG_CONTENT 无效。 - 如果不存在具有相同 TAG_NAME 的结束标签，则开始标签不匹配，反之亦然。但是，在标签嵌套时，还需要考虑不平衡问题。
- 如果找不到后续的
>，则<不匹配。当找到<或</时，直到下一个>的所有后续字符都应解析为 TAG_NAME（不一定有效）。 - cdata 具有以下格式：
<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围定义为<![CDATA[和第一个后续]]>之间的字符。 - CDATA_CONTENT 可能包含任何字符。cdata 的功能是禁止验证器解析 CDATA_CONTENT，因此即使它有一些可以解析为标签的字符（无论有效还是无效），你都应该将其视为常规字符。
示例 1:
输入: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
输出: true
示例 2:
输入: code = "<DIV>>> ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
输出: true
示例 3:
输入: code = "<A> <B> </A> </B>"
输出: false
约束:
- 1 <= code.length <= 500
- code 由英文字母、数字、’<’、’>’、’/’、’!’、’[’、’]’、’.’ 和 ’ ’ 组成。
解题思路
这是一个复杂的字符串解析问题，需要模拟标签验证的整个过程。
核心思路：
- 使用栈来跟踪标签的匹配情况
- 逐字符解析，识别不同类型的标签和内容
- 特殊处理 CDATA 部分，跳过其内容的解析
解析策略：
- 首先检查代码是否被有效的闭合标签包围
- 使用栈记录遇到的开始标签
- 遇到结束标签时，检查是否与栈顶的开始标签匹配
- 对于 CDATA，直接跳过到
]]>结束位置 - 验证标签名是否符合规则（1-9个大写字母）
关键难点：
- 正确解析各种标签格式
- 处理嵌套标签的平衡性
- CDATA 内容的特殊处理
- 边界情况的处理（如不完整的标签）
算法流程：
- 移除最外层标签，验证其有效性
- 使用栈和索引遍历内容
- 遇到
<时判断是开始标签、结束标签还是 CDATA - 验证标签名的有效性
- 确保所有标签都正确匹配
这种方法能够准确处理所有边界情况，包括嵌套标签、CDATA 和各种非法格式。
代码实现
class Solution {
public:
bool isValid(string code) {
stack<string> st;
int i = 0;
while (i < code.length()) {
if (i == 0 || !st.empty()) {
if (code[i] == '<') {
if (i + 8 < code.length() && code.substr(i, 9) == "<![CDATA[") {
// Handle CDATA
int j = i + 9;
while (j + 2 < code.length() && code.substr(j, 3) != "]]>") {
j++;
}
if (j + 2 >= code.length()) return false;
i = j + 3;
} else {
// Handle tag
int j = i + 1;
bool isClosing = false;
if (j < code.length() && code[j] == '/') {
isClosing = true;
j++;
}
int tagStart = j;
while (j < code.length() && code[j] != '>') {
if (!isalpha(code[j]) || !isupper(code[j])) return false;
j++;
}
if (j >= code.length()) return false;
string tagName = code.substr(tagStart, j - tagStart);
if (tagName.length() == 0 || tagName.length() > 9) return false;
if (isClosing) {
if (st.empty() || st.top() != tagName) return false;
st.pop();
} else {
st.push(tagName);
}
i = j + 1;
}
} else {
i++;
}
} else {
return false;
}
}
return st.empty();
}
};
class Solution:
def isValid(self, code: str) -> bool:
stack = []
i = 0
while i < len(code):
if i == 0 or stack:
if code[i] == '<':
if i + 8 < len(code) and code[i:i+9] == "<![CDATA[":
# Handle CDATA
j = i + 9
while j + 2 < len(code) and code[j:j+3] != "]]>":
j += 1
if j + 2 >= len(code):
return False
i = j + 3
else:
# Handle tag
j = i + 1
is_closing = False
if j < len(code) and code[j] == '/':
is_closing = True
j += 1
tag_start = j
while j < len(code) and code[j] != '>':
if not code[j].isupper():
return False
j += 1
if j >= len(code):
return False
tag_name = code[tag_start:j]
if len(tag_name) == 0 or len(tag_name) > 9:
return False
if is_closing:
if not stack or stack[-1] != tag_name:
return False
stack.pop()
else:
stack.append(tag_name)
i = j + 1
else:
i += 1
else:
return False
return len(stack) == 0
public class Solution {
public bool IsValid(string code) {
var stack = new Stack<string>();
int i = 0;
while (i < code.Length) {
if (i == 0 || stack.Count > 0) {
if (code[i] == '<') {
if (i + 8 < code.Length && code.Substring(i, 9) == "<![CDATA[") {
// Handle CDATA
int j = i + 9;
while (j + 2 < code.Length && code.Substring(j, 3) != "]]>") {
j++;
}
if (j + 2 >= code.Length) return false;
i = j + 3;
} else {
// Handle tag
int j = i + 1;
bool isClosing = false;
if (j < code.Length && code[j] == '/') {
isClosing = true;
j++;
}
int tagStart = j;
while (j < code.Length && code[j] != '>') {
if (!char.IsUpper(code[j])) return false;
j++;
}
if (j >= code.Length) return false;
string tagName = code.Substring(tagStart, j - tagStart);
if (tagName.Length == 0 || tagName.Length > 9) return false;
if (isClosing) {
if (stack.Count == 0 || stack.Peek() != tagName) return false;
stack.Pop();
} else {
stack.Push(tagName);
}
i = j + 1;
}
} else {
i++;
}
} else {
return false;
}
}
return stack.Count == 0;
}
}
var isValid = function(code) {
const stack = [];
let i = 0;
while (i < code.length) {
if (i == 0 || stack.length > 0) {
if (code.startsWith('<![CDATA[', i)) {
let j = code.indexOf(']]>', i + 9);
if (j == -1) return false;
i = j + 3;
} else if (code.startsWith('</', i)) {
let j = i + 2;
while (j < code.length && code[j] != '>') j++;
if (j == code.length) return false;
let tagName = code.substring(i + 2, j);
if (!isValidTagName(tagName) || stack.length == 0 || stack.pop() != tagName) {
return false;
}
i = j + 1;
} else if (code[i] == '<') {
let j = i + 1;
while (j < code.length && code[j] != '>') j++;
if (j == code.length) return false;
let tagName = code.substring(i + 1, j);
if (!isValidTagName(tagName)) return false;
stack.push(tagName);
i = j + 1;
} else {
i++;
}
} else {
return false;
}
}
return stack.length == 0;
};
function isValidTagName(tagName) {
if (tagName.length < 1 || tagName.length > 9) return false;
for (let c of tagName) {
if (c < 'A' || c > 'Z') return false;
}
return true;
}
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 需要遍历整个字符串一次，其中 n 是字符串长度 |
| 空间复杂度 | O(n) | 在最坏情况下，栈可能存储所有的开始标签 |
相关题目
- . Add Bold Tag in String (Medium)