591. 标签验证器 : 字符串模拟
发布网友
发布时间：11小时前
共1个回答
热心网友
时间：9小时前
这是 LeetCode 上的 591. 标签验证器 ，难度为 困难。
Tag : 「模拟」、「栈」
给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：
代码必须被合法的闭合标签包围。否则，代码是无效的。
闭合标签（不一定合法）要严格符合格式：<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?（ 请参考规则 $7$ ）和任意字符（ 注意参考规则 $1$ ）除了不匹配的 <、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，TAG_CONTENT?是不合法的。
一个起始标签，如果没有具有相同?TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
一个 <，如果你找不到一个后续的 > 与之匹配，是不合法的。并且当你找到一个 < 或</ 时，所有直到下一个 > 的前的字符，都应当被解析为?TAG_NAME（不一定合法）。
cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT?的范围被定义成?<![CDATA[?和后续的第一个?]]>之间的字符。
CDATA_CONTENT?可以包含任意字符。cdata 的功能是阻止验证器解析 CDATA_CONTENT，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。
合法代码的例子:
输入:?"<DIV>This?is?the?first?line?<![CDATA[<div>]]></DIV>"输出:?True解释:?代码被包含在了闭合的标签内：?<DIV>?和?</DIV>?。TAG_NAME?是合法的，TAG_CONTENT?包含了一些字符和?cdata?。?即使?CDATA_CONTENT?含有不匹配的起始标签和不合法的?TAG_NAME，它应该被视为普通的文本，而不是标签。所以?TAG_CONTENT?是合法的，因此代码是合法的。最终返回True。输入:?"<DIV>>>??![cdata[]]?<![CDATA[<div>]>]]>]]>>]</DIV>"输出:?True解释:我们首先将代码分割为：?start_tag|tag_content|end_tag?。start_tag?->?"<DIV>"end_tag?->?"</DIV>"tag_content?也可被分割为：?text1|cdata|text2?。text1?->?">>??![cdata[]]?"cdata?->?"<![CDATA[<div>]>]]>"?，其中?CDATA_CONTENT?为?"<div>]>"text2?->?"]]>>]"start_tag?不是?"<DIV>>>"?的原因参照规则?6?。cdata?不是?"<![CDATA[<div>]>]]>]]>"?的原因参照规则?7?。不合法代码的例子:
输入:?"<A>??<B>?</A>???</B>"输出:?False解释:?不合法。如果?"<A>"?是闭合的，那么?"<B>"?一定是不匹配的，反之亦然。输入:?"<DIV>??div?tag?is?not?closed??<DIV>"输出:?False输入:?"<DIV>??unmatched?<??</DIV>"输出:?False输入:?"<DIV>?closed?tags?with?invalid?tag?name??<b>123</b>?</DIV>"输出:?False输入:?"<DIV>?unmatched?tags?with?invalid?tag?name??</1234567890>?and?<CDATA[[]]>??</DIV>"输出:?False输入:?"<DIV>??unmatched?start?tag?<B>??and?unmatched?end?tag?</C>??</DIV>"输出:?False注意:
为简明起见，你可以假设输入的代码（包括提到的任意字符）只包含数字, 字母, '<','>','/','!','[',']'和' '。
模拟（栈）字符串大模拟，假设字符串 s 长度为 $n$，当前处理到的位置为 $i$，根据以下优先级进行检查：
优先尝试检查以 $i$ 为开始的连续段是否为 CDATA，若能匹配到开头，则尝试匹配到 CDATA 的结尾处，并更新 $i$，若无法找到结尾，返回 False；
尝试匹配 $s[i]$ 是否为 <，若满足，则根据 $s[i + 1]$ 是否为 / 来判断当前 TAG_NAME 是处于右边还是左边，然后将 TAG_NAME 取出，记为 $tag$，判断 $tag$ 长度是否合法，不合法返回 False，合法则根据是左边还是右边的 TAG_NAME 分情况讨论：
位于左边的 TAG_NAME：将其加入栈中，等待右边的 TAG_NAME 与其匹配；
位于右边的 TAG_NAME：将其与当前栈顶的元素进行匹配，若栈为空或匹配不上，返回 False（注意：由于整个 s 应当被一对 TAG_NAME 所包裹，因此如果取出后栈顶元素匹配后，栈为空，同时又还没处理完整个 s，此时 s 也不合法，返回 Fasle）；
其余情况则为普通字符。
最后由于整个 s 应当被一对 TAG_NAME 所包裹，因此当 $i = 0$ 时，不能是情况 $1$ 和情况 $3$，需要特判一下。
代码：
class?Solution?{????String?CDATA1?=?"<![CDATA[",?CDATA2?=?"]]>";????public?boolean?isValid(String?s)?{????????Deque<String>?d?=?new?ArrayDeque<>();????????int?n?=?s.length(),?i?=?0;????????while?(i?<?n)?{????????????if?(i?+?8?<?n?&&?s.substring(i,?i?+?9).equals(CDATA1))?{????????????????if?(i?==?0)?return?false;????????????????int?j?=?i?+?9;????????????????boolean?ok?=?false;????????????????while?(j?<?n?&&?!ok)?{????????????????????if?(j?+?2?<?n?&&?s.substring(j,?j?+?3).equals(CDATA2))?{????????????????????????j?=?j?+?3;?ok?=?true;????????????????????}?else?{????????????????????????j++;????????????????????}????????????????}????????????????if?(!ok)?return?false;????????????????i?=?j;????????????}?else?if?(s.charAt(i)?==?'<')?{????????????????if?(i?==?n?-?1)?return?false;????????????????boolean?isEnd?=?s.charAt(i?+?1)?==?'/';????????????????int?p?=?isEnd???i?+?2?:?i?+?1,?j?=?p;????????????????while?(j?<?n?&&?s.charAt(j)?!=?'>')?{????????????????????if?(!Character.isUpperCase(s.charAt(j)))?return?false;????????????????????j++;????????????????}????????????????if?(j?==?n)?return?false;????????????????int?len?=?j?-?p;????????????????if?(len?<?1?||?len?>?9)?return?false;????????????????String?tag?=?s.substring(p,?j);????????????????i?=?j?+?1;????????????????if?(!isEnd)?{????????????????????d.addLast(tag);????????????????}?else?{????????????????????if?(d.isEmpty()?||?!d.pollLast().equals(tag))?return?false;????????????????????if?(d.isEmpty()?&&?i?<?n)?return?false;????????????????}????????????}?else?{????????????????if?(i?==?0)?return?false;????????????????i++;????????????}????????}????????return?d.isEmpty();????}}时间复杂度：$O(n)$
空间复杂度：$O(n)$
最后这是我们「刷穿 LeetCode」系列文章的第 No.591 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
