题目

标题和出处

标题：标签验证器

出处：591. 标签验证器

难度

7 级

题目描述

要求

给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。

合法的代码片段需要遵守以下的所有规则：

1. 代码必须被合法的闭合标签包围。否则，代码是无效的。
2. 闭合标签（不一定合法）要严格符合格式：$\text{TAG\_CONTENT}$。其中， \texttt{} 是起始标签， \texttt{} 是结束标签。起始和结束标签中的 $\text{TAG\_NAME}$ 应当相同。当且仅当 $\text{TAG\_NAME}$ 和 $\text{TAG\_CONTENT}$ 都是合法的，闭合标签才是合法的。
3. 合法的 $\text{TAG\_NAME}$ 仅含有大写字母，长度在范围 $\text{[1,9]}$ 之间。否则，该 $\text{TAG\_NAME}$ 是不合法的。
4. 合法的 $\text{TAG\_CONTENT}$ 可以包含其他合法的闭合标签、$\text{cdata}$ 和任意字符（参考规则 1），除了不匹配的 $\text{<}$、不匹配的起始和结束标签、不匹配的或带有不合法 $\text{TAG\_NAME}$ 的闭合标签。否则，$\text{TAG\_CONTENT}$ 是不合法的。
5. 一个起始标签，如果没有具有相同 $\text{TAG\_NAME}$ 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
6. 一个 $\text{<}$，如果你找不到一个后续的 $\text{>}$ 与之匹配，是不合法的。并且当你找到一个 $\text{<}$ 或 时，所有直到下一个 > \texttt{>} > 之前的字符，都应当被解析为 TAG_NAME \texttt{TAG\_NAME} TAG_NAME（不一定合法）。
7. $\text{cdata}$ 有如下格式： \texttt{} 。$\text{CDATA\_CONTENT}$ 的范围被定义成 和后续的第一个 ]]> \texttt{]]>} ]]> 之间的字符。
8. $\text{CDATA\_CONTENT}$ 可以包含任意字符。$\text{cdata}$ 的功能是阻止验证器解析 $\text{CDATA\_CONTENT}$，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。

示例

示例 1：

输入： code   =   "

" \texttt{code = ""} code = "

This is the first line ]]>

"
输出：$\text{true}$
解释：
代码被包含在了闭合的标签内：$\text{和 texttt{}$。
$\text{TAG\_NAME}$ 是合法的，$\text{TAG\_CONTENT}$ 包含了一些字符和 $\text{cdata}$。
虽然 $\text{CDATA\_CONTENT}$ 含有不匹配的起始标签和不合法的 $\text{TAG\_NAME}$，它应该被视为普通的文本，而不是标签。
所以 $\text{TAG\_CONTENT}$ 是合法的，因此代码是合法的。返回 $\text{true}$。

示例 2：

输入： code   =   "

" \texttt{code = ""} code = "

>> ![cdata[]] ]>]]>]]>>]

"
输出：$\text{true}$
解释：
我们首先将代码分割为：$\text{start\_tag|tag\_content|end\_tag}$。
$\text{start\_tag}\to \text{"" end\_tag → "" texttt{end\_tag} rightarrow texttt{"}$
$\text{tag\_content}$ 也可被分割为：$\text{text1|cdata|text2}$。
$\text{text1}\to \text{">> ![cdata[]] "}$
$\text{cdata}\to \text{"]>]]>"}$，其中 $\text{CDATA\_CONTENT}$ 为 $"]>" text2 → "]]>>]" \texttt{text2} \rightarrow \texttt{"]]>>]"} text2→"]]>>]" start_tag \texttt{start\_tag} start_tag 不是 ">>" \texttt{">>"} ">>" 的原因参照规则 6。 cdata \texttt{cdata} cdata 不是 "]>]]>]]>" \texttt{"]>]]>]]>"} "]>]]>]]>" 的原因参照规则 7。 示例 3： 输入： code   =   "          " \texttt{code = "~~~~~~"} code = "      " 输出： false \texttt{false} false 解释：不合法。如果 "" \texttt{""} "" 是闭合的，那么 "" \texttt{""} "" 一定是不匹配的，反之亦然。 数据范围 1 ≤ code.length ≤ 500 \texttt{1} \le \texttt{code.length} \le \texttt{500} 1≤code.length≤500输入的代码由英语字母、数字、 ‘<’ \texttt{`<'} ‘<’、 ‘>’ \texttt{`>'} ‘>’、 ‘/’ \texttt{`/'} ‘/’、 ‘!’ \texttt{`!'} ‘!’、 ‘[’ \texttt{`['} ‘[’、 ‘]’ \texttt{`]'} ‘]’、 ‘.’ \texttt{`.'} ‘.’ 和 ‘   ’ \texttt{` '} ‘ ’ 组成 解法 思路和算法 这道题要求验证给定的表示代码片段的字符串 code \textit{code} code 是否为合法的标签。验证时需要重点关注的是起始标签、结束标签和 cdata \text{cdata} cdata。 由于标签可以嵌套，每个结束标签只能和最后一个出现的未匹配的起始标签匹配，匹配顺序符合栈的「后进先出」的规则，因此可以使用栈验证标签。从左到右遍历代码片段，遇到起始标签则入栈，遇到结束标签则判断是否和栈顶的起始标签匹配，如果匹配则将起始标签出栈，如果不匹配则代码片段不是有效的标签。 由于整个代码片段必须被合法的闭合标签包围，因此代码片段中的任何字符都必须属于闭合标签的一部分。如果存在一个字符在最外层闭合标签以外，则一定不是合法的标签。判断的方法是，如果当下标大于 0 0 0 且小于字符串长度时，栈为空，则说明存在一个字符在最外层闭合标签以外，返回 false \text{false} false。 对于其余情况，只需要判断是否遇到起始标签、结束标签和 cdata \text{cdata} cdata 即可。验证时，首先要检查起始标签、结束标签和 cdata \text{cdata} cdata 是否完整（即能找到开始标志和结束标志），然后验证内容是否合法： 对于起始标签，标签名应满足全部是大写字母且长度在 [ 1 , 9 ] [1, 9] [1,9] 范围内； 对于结束标签，标签名应和最近一个未匹配的起始标签的标签名相同，此时不需要验证标签名的合法性，因为标签名的合法性在起始标签中已经被验证； 对于 cdata \text{cdata} cdata，只需要符合格式即可，不需要验证内容。 具体实现方面，由于 cdata \text{cdata} cdata 的前 9 9 9 个字符确定，结束标签的前 2 2 2 个字符确定，开始标签的前 1 1 1 个标签确定，因此可以依次判断是否遇到 cdata \text{cdata} cdata、结束标签和起始标签。 不同类型的元素的验证方法如下。 对于 cdata \text{cdata} cdata 的判断，如果遇到连续的 9 9 9 个字符等于 ""，则是 cdata \text{cdata} cdata 的起始位置，在起始位置之后的第一个 "]]>" \texttt{"]]>"} "]]>" 是 cdata \text{cdata} cdata 的结束位置。 如果在 "" 之后找不到 "]]>" \texttt{"]]>"} "]]>"，则 cdata \text{cdata} cdata 是无效的，返回 false \text{false} false。如果在 "" 之后找到 "]]>" \texttt{"]]>"} "]]>"，则从起始位置到结束位置的部分都是 cdata \text{cdata} cdata 的内容，将下标移动到结束位置之后。 对于结束标签的判断，如果遇到连续的 2 2 2 个字符等于 ""，则是结束标签的起始位置，在起始位置之后的第一个 ">" \texttt{">"} ">" 是结束标签的结束位置。 如果在 "" 之后找不到 ">" \texttt{">"} ">"，则结束标签是无效的，返回 false \text{false} false。如果在 "" 之后找到 ">" \texttt{">"} ">"，则在起始位置和结束位置之间的内容是结束标签的标签名，此时与当前结束标签匹配的起始标签的标签名应该位于栈顶，如果栈为空或者栈顶元素和结束标签的标签名不相等，则匹配失败，返回 false \text{false} false，如果栈顶元素和结束标签的标签名相等，则将栈顶元素出栈，并将下标移动到结束位置之后。 对于起始标签的判断，如果遇到字符 "<" \texttt{"<"} "<"，则是起始标签的起始位置，在起始位置之后的第一个 ">" \texttt{">"} ">" 是起始标签的结束位置。结束标签的起始位置，在起始位置之后的第一个 ">" \texttt{">"} ">" 是结束标签的结束位置。 如果在 "<" \texttt{"<"} "<" 之后找不到 ">" \texttt{">"} ">"，则起始标签是无效的，返回 false \text{false} false。如果在 "<" \texttt{"<"} "<" 之后找到 ">" \texttt{">"} ">"，则在起始位置和结束位置之间的内容是起始标签的标签名，此时需要判断标签名是否合法，合法的标签名满足长度在范围 [ 1 , 9 ] [1, 9] [1,9] 内且全部是大写字母，如果标签名不合法则返回 false \text{false} false，如果标签名合法则将标签名入栈，并将下标移动到结束位置之后。 除了 cdata \text{cdata} cdata、结束标签和起始标签以外，其余的字符均为某个标签内部的内容，因此不需要验证。 遍历结束时，所有的起始标签都应该被结束标签匹配，此时栈为空。当栈为空时返回 true \text{true} true，否则返回 false \text{false} false。 代码 class Solution { public boolean isValid(String code) { final int CDATA_START_LENGTH = 9, CDATA_END_LENGTH = 3, END_TAG_LENGTH = 2; Deque<String> stack = new ArrayDeque<String>(); int length = code.length(); int index = 0; while (index < length) { if (index > 0 && stack.isEmpty()) { return false; } if (index + CDATA_START_LENGTH <= length && code.substring(index, index + CDATA_START_LENGTH).equals(")) { index += CDATA_START_LENGTH; while (index <= length - CDATA_END_LENGTH && !code.substring(index, index + CDATA_END_LENGTH).equals("]]>")) { index++; } if (index > length - CDATA_END_LENGTH) { return false; } index += CDATA_END_LENGTH; } else if (index + END_TAG_LENGTH <= length && code.substring(index, index + END_TAG_LENGTH).equals(")) { index += END_TAG_LENGTH; int start = index; while (index < length && code.charAt(index) != '>') { index++; } if (index >= length) { return false; } String tag = code.substring(start, index); if (stack.isEmpty() || !stack.peek().equals(tag)) { return false; } stack.pop(); index++; } else if (code.charAt(index) == '<') { index++; int start = index; while (index < length && code.charAt(index) != '>') { index++; } if (index >= length || index == start || index - start > 9) { return false; } for (int i = start; i < index; i++) { char c = code.charAt(i); if (c < 'A' || c > 'Z') { return false; } } String tag = code.substring(start, index); stack.push(tag); index++; } else { index++; } } return stack.isEmpty(); } } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859 复杂度分析 时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 code \textit{code} code 的长度。需要遍历字符串数组一次，原始输入中的每个字符的操作时间都是 O ( 1 ) O(1) O(1)。 空间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 code \textit{code} code 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过 n n n。 $