Java教程

力扣591(java)-标签验证器(困难)

本文主要是介绍力扣591(java)-标签验证器(困难),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

给定一个表示代码片段的字符串,你需要实现一个验证器来解析这段代码,并返回它是否合法。合法的代码片段需要遵守以下的所有规则:

  1. 代码必须被合法的闭合标签包围。否则,代码是无效的。
  2. 闭合标签(不一定合法)要严格符合格式:<TAG_NAME>TAG_CONTENT</TAG_NAME>。其中,<TAG_NAME>是起始标签,</TAG_NAME>是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都是合法的,闭合标签才是合法的。
  3. 合法的 TAG_NAME 仅含有大写字母,长度在范围 [1,9] 之间。否则,该 TAG_NAME 是不合法的。
  4. 合法的 TAG_CONTENT 可以包含其他合法的闭合标签,cdata (请参考规则7)和任意字符(注意参考规则1)除了不匹配的<、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则,TAG_CONTENT 是不合法的。
  5. 一个起始标签,如果没有具有相同 TAG_NAME 的结束标签与之匹配,是不合法的。反之亦然。不过,你也需要考虑标签嵌套的问题。
  6. 一个<,如果你找不到一个后续的>与之匹配,是不合法的。并且当你找到一个<或</时,所有直到下一个>的前的字符,都应当被解析为 TAG_NAME(不一定合法)。
  7. cdata 有如下格式:<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。
  8. 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
注意:

为简明起见,你可以假设输入的代码(包括提到的任意字符)只包含数字, 字母, '<','>','/','!','[',']'和' '。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/tag-validator
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

这题的题目实在是太太太长了,参考@宫水三叶的题解以及其他大佬的题解,梳理一下思路~,感觉自己有所成长,一步一步分析,有些代码有所变换,也能一步一步试错进行通过啦(:

仍然使用栈的特点来解题

1.使用栈来存储有效的左标签,并在找到右标签时与栈顶的左标签进行比较。

2.遍历遇到 <时,根据遇到的是左标签<TAG_NAME>、右标签</TAG_NAME>、cdata<![CDATA[任意字符]]>分情况讨论:

  • 遇到的是左标签:检查名字是否均为大写字母且长度在[1,9],不符合条件就返回false,符合条件就压栈,等待与之匹配的右标签;
  • 遇到的是右标签:将其与栈顶元素进行匹配,若栈为空或者不匹配,返回false,匹配后栈顶元素出栈;
  • 遇到的是cdata:检查当前连续段是否为cdata,若能匹配到开头--"<![CDATA[",则尝试匹配到cdata的结尾 "]]>",若无法找到结尾,返回 false

3.遍历完后,判断栈是否为空,来返回是true还是fasle。

代码:

 1 class Solution {
 2     public boolean isValid(String code) {
 3         int n = code.length();
 4         if(code == null || n == 0) return false;
 5         Deque<String> stack = new ArrayDeque<>();
 6         //不在这里变化i的原因:每一个判断中i的变化分情况讨论
 7         for(int i = 0; i < n; ){
 8             if(code.charAt(i) == '<'){
 9                 //如果这时<已经在末位置
10                 if(i == n - 1){
11                     return false;
12                 }else if(code.charAt(i+1) == '/'){
13                     //如果这时候为末标签
14                     //从i处开始检索 > 首次出现的位置
15                     //</TAG> i对应<  j对应>
16                     int j = code.indexOf('>', i);
17                     //未找到返回-1
18                     if(j == -1) return false;
19                     //找到了就去栈中判断是否有对应的首标签
20                     String tag = code.substring(i + 2, j);
21                     if(stack.isEmpty() || !stack.peekLast().equals(tag)){
22                         return false;
23                      }
24                     //匹配成功,就将该首标签弹出栈
25                     stack.pollLast();
26                     //更新i的位置
27                     i = j + 1;
28                     //如果这时栈空且未达到末位置也为fasle
29                     if(stack.isEmpty() && i != n) return false;
30                 }else if(code.charAt(i + 1) == '!'){
31                     //这时候为cdata
32                     //cdata = <![CDATA[任意内容]]>
33                     //如果这时候占位空,就没标签包含cdata
34                     if(stack.isEmpty()) return false;
35                     //<![CDATA[ 长度为9
36                     if(i + 9 > n) return false;
37                     //取出感叹号后面的7个字符
38                     String cdata1 = code.substring(i + 2, i + 9);
39                     if(!"[CDATA[".equals(cdata1)) return false;
40                     //找到 ]]> 的位置
41                     int j = code.indexOf("]]>", i);
42                     if(j == -1) return false;
43                     i = j + 3;
44                 }else{
45                     //首标签,i对应< , j对应>
46                     int j = code.indexOf('>', i);
47                     //判断标签中名字长度的合法性
48                     if(j < 0 || j - i - 1 < 1 || j - i - 1 > 9) return false;
49                      //判断标签中名字是否全为大写字母
50                     for(int k = i + 1; k < j; k++){
51                         if(!Character.isUpperCase(code.charAt(k))){
52                             return false;
53                         }
54                     }
55                     //将首标签压栈
56                     stack.addLast(code.substring(i + 1, j));
57                     //更新i
58                     i = j + 1;
59                 }  
60             }else{
61                 //如果不为 <,说明是其他字符,栈中就应该有首标签
62                 if(stack.isEmpty()) return false;
63                 //接着下一个字符进行遍历
64                 i++;
65             }
66         }
67         return stack.isEmpty();
68     }
69 }

小知识:

1.indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。注意:该方法对大小写敏感!

stringObject.indexOf( value, index );

参数:

value:必需,规定需检索的字符串值。可选的整数参数。

index:规定在字符串中开始检索的位置。它的合法取值是 0 到 stringObject.length - 1。如省略该参数,则将从字符串的首字符开始检索。该方法将从头到尾地检索字符串 stringObject,看它是否含有子串 value。开始检索的位置在字符串的 index 处或字符串的开头(没有指定 index 时)。stringObject 中的字符位置是从 0 开始的,如果找到一个 value,则返回 value 的第一次出现的位置。如果没找到,则返回-1。

2.substring(int beginIndex, int endIndex):返回从起始位置到目标位置直接的字符串,不包含目标位置。(左闭右开区间)。

这篇关于力扣591(java)-标签验证器(困难)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!