[Swift]LeetCode591. 标签验证器 | Tag Validator

2024-04-05 10:08:36

Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold: 

  1. The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
  2. A closed tag (not necessarily valid) has exactly the following format : <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
  3. A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
  4. A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.
  5. A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
  6. A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME (not necessarily valid).
  7. The cdata has the following format : <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent ]]>.
  8. CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

Valid Code Examples:

Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"

Output: True

Explanation: 

The code is wrapped in a closed tag : <DIV> and </DIV>. 

The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata. 

Although CDATA_CONTENT has unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag.

So TAG_CONTENT is valid, and then the code is valid. Thus return true.


Input: "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"

Output: True

Explanation:

We first separate the code into : start_tag|tag_content|end_tag.

start_tag -> "<DIV>"

end_tag -> "</DIV>"

tag_content could also be separated into : text1|cdata|text2.

text1 -> ">>  ![cdata[]] "

cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>"

text2 -> "]]>>]"


The reason why start_tag is NOT "<DIV>>>" is because of the rule 6.
The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7. 

Invalid Code Examples:

Input: "<A>  <B> </A>   </B>"
Output: False
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.

Input: "<DIV>  div tag is not closed  <DIV>"
Output: False

Input: "<DIV>  unmatched <  </DIV>"
Output: False

Input: "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
Output: False

Input: "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
Output: False

Input: "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
Output: False 

Note:

  1. For simplicity, you could assume the input code (including the any characters mentioned above) only contain letters, digits, '<','>','/','!','[',']' and ' '.

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

  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

注意:

  1. 为简明起见，你可以假设输入的代码（包括提到的任意字符）只包含数字, 字母, '<','>','/','!','[',']'和' '。
Runtime: 20 ms Memory Usage: 19.8 MB 
 1 class Solution {
 2     func isValid(_ code: String) -> Bool {
 3         var st:[String] = [String]()
 4         var i:Int = 0
 5         while(i < code.count)
 6         {            
 7             if i > 0 && st.isEmpty
 8             {
 9                 return false                
10             }
11             if code.subString(i, 9) == "<![CDATA["
12             {
13                 var j:Int = i + 9
14                 i = code.find("]]>",j)
15                 if i < 0 {return false}
16                 i += 2
17             }
18             else if code.subString(i, 2) == "</"
19             {
20                 var j:Int = i + 2
21                 i = code.find(">",j)
22                 if i < 0 {return false}
23                 var tag:String = code.subString(j, i - j)
24                 if st.isEmpty || st.last! != tag
25                 {
26                     return false
27                 }
28                 st.popLast()
29             }
30             else if code.subString(i, 1) == "<"
31             {
32                 var j:Int = i + 1
33                 i = code.find(">",j)
34                 if i < 0 || i == j || i - j > 9
35                 {
36                     return false
37                 }
38                 for k in j..<i
39                 {
40                     if code[k] < "A" || code[k] > "Z"
41                     {
42                         return false
43                     }                    
44                 }
45                 var tag:String = code.subString(j, i - j)
46                 st.append(tag)
47             }    
48             i += 1
49         }
50         return st.isEmpty
51     } 
52 }
53 
54 //String扩展
55 extension String {
56     //subscript函数可以检索数组中的值
57     //直接按照索引方式截取指定索引的字符
58     subscript (_ i: Int) -> Character {
59         //读取字符
60         get {return self[index(startIndex, offsetBy: i)]}
61     }
62         
63     // 截取字符串：指定索引和字符数
64     // - begin: 开始截取处索引
65     // - count: 截取的字符数量
66     func subString(_ begin:Int,_ count:Int) -> String {
67         let start = self.index(self.startIndex, offsetBy: max(0, begin))
68         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
69         return String(self[start..<end]) 
70     }
71 
72     // 截取字符串：从index到结束处
73     // - Parameter index: 开始索引
74     // - Returns: 子字符串
75     func subStringFrom(_ index: Int) -> String {
76         let theIndex = self.index(self.endIndex, offsetBy: index - self.count)
77         return String(self[theIndex..<endIndex])
78     }
79     
80     //从0索引处开始查找是否包含指定的字符串，返回Int类型的索引
81     //返回第一次出现的指定子字符串在此字符串中的索引
82     func find(_ sub:String)->Int {
83         var pos = -1
84         if let range = range(of:sub, options: .literal ) {
85             if !range.isEmpty {
86                 pos = self.distance(from:startIndex, to:range.lowerBound)
87             }
88         }
89         return pos
90     }
91     
92     //从指定索引处开始查找是否包含指定的字符串，返回Int类型的索引
93     //返回第一次出现的指定子字符串在此字符串中的索引
94     func find(_ sub:String,_ begin:Int)->Int {
95         var str:String = self.subStringFrom(begin)
96         var pos:Int = str.find(sub)
97         return pos == -1 ? -1 : (pos + begin)
98     }
99 }

 

上一篇：Hibernate Validator


下一篇：Code-Validator：验证整数