Description#
Given a string representing a code snippet, 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:
- The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
- 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. - A valid
TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid. - 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. - 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.
- 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). - 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 ]]>. 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.
Example 1:
Input: code = "<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 an unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as a tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.
Example 2:
Input: code = "<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.
Example 3:
Input: code = "<A> <B> </A> </B>"
Output: false
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.
Constraints:
1 <= code.length <= 500code consists of English letters, digits, '<', '>', '/', '!', '[', ']', '.', and ' '.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution:
def isValid(self, code: str) -> bool:
def check(tag):
return 1 <= len(tag) <= 9 and all(c.isupper() for c in tag)
stk = []
i, n = 0, len(code)
while i < n:
if i and not stk:
return False
if code[i : i + 9] == '<![CDATA[':
i = code.find(']]>', i + 9)
if i < 0:
return False
i += 2
elif code[i : i + 2] == '</':
j = i + 2
i = code.find('>', j)
if i < 0:
return False
t = code[j:i]
if not check(t) or not stk or stk.pop() != t:
return False
elif code[i] == '<':
j = i + 1
i = code.find('>', j)
if i < 0:
return False
t = code[j:i]
if not check(t):
return False
stk.append(t)
i += 1
return not stk
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
public boolean isValid(String code) {
Deque<String> stk = new ArrayDeque<>();
for (int i = 0; i < code.length(); ++i) {
if (i > 0 && stk.isEmpty()) {
return false;
}
if (code.startsWith("<![CDATA[", i)) {
i = code.indexOf("]]>", i + 9);
if (i < 0) {
return false;
}
i += 2;
} else if (code.startsWith("</", i)) {
int j = i + 2;
i = code.indexOf(">", j);
if (i < 0) {
return false;
}
String t = code.substring(j, i);
if (!check(t) || stk.isEmpty() || !stk.pop().equals(t)) {
return false;
}
} else if (code.startsWith("<", i)) {
int j = i + 1;
i = code.indexOf(">", j);
if (i < 0) {
return false;
}
String t = code.substring(j, i);
if (!check(t)) {
return false;
}
stk.push(t);
}
}
return stk.isEmpty();
}
private boolean check(String tag) {
int n = tag.length();
if (n < 1 || n > 9) {
return false;
}
for (char c : tag.toCharArray()) {
if (!Character.isUpperCase(c)) {
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
bool isValid(string code) {
stack<string> stk;
for (int i = 0; i < code.size(); ++i) {
if (i && stk.empty()) return false;
if (code.substr(i, 9) == "<![CDATA[") {
i = code.find("]]>", i + 9);
if (i < 0) return false;
i += 2;
} else if (code.substr(i, 2) == "</") {
int j = i + 2;
i = code.find('>', j);
if (i < 0) return false;
string t = code.substr(j, i - j);
if (!check(t) || stk.empty() || stk.top() != t) return false;
stk.pop();
} else if (code.substr(i, 1) == "<") {
int j = i + 1;
i = code.find('>', j);
if (i < 0) return false;
string t = code.substr(j, i - j);
if (!check(t)) return false;
stk.push(t);
}
}
return stk.empty();
}
bool check(string tag) {
int n = tag.size();
if (n < 1 || n > 9) return false;
for (char& c : tag)
if (!isupper(c))
return false;
return true;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| func isValid(code string) bool {
var stk []string
for i := 0; i < len(code); i++ {
if i > 0 && len(stk) == 0 {
return false
}
if strings.HasPrefix(code[i:], "<![CDATA[") {
n := strings.Index(code[i+9:], "]]>")
if n == -1 {
return false
}
i += n + 11
} else if strings.HasPrefix(code[i:], "</") {
if len(stk) == 0 {
return false
}
j := i + 2
n := strings.IndexByte(code[j:], '>')
if n == -1 {
return false
}
t := code[j : j+n]
last := stk[len(stk)-1]
stk = stk[:len(stk)-1]
if !check(t) || last != t {
return false
}
i += n + 2
} else if strings.HasPrefix(code[i:], "<") {
j := i + 1
n := strings.IndexByte(code[j:], '>')
if n == -1 {
return false
}
t := code[j : j+n]
if !check(t) {
return false
}
stk = append(stk, t)
i += n + 1
}
}
return len(stk) == 0
}
func check(tag string) bool {
n := len(tag)
if n < 1 || n > 9 {
return false
}
for _, c := range tag {
if c < 'A' || c > 'Z' {
return false
}
}
return true
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| impl Solution {
pub fn is_valid(code: String) -> bool {
fn check(tag: &str) -> bool {
let n = tag.len();
n >= 1 &&
n <= 9 &&
tag
.as_bytes()
.iter()
.all(|b| b.is_ascii_uppercase())
}
let mut stk = Vec::new();
let mut i = 0;
while i < code.len() {
if i > 0 && stk.is_empty() {
return false;
}
if code[i..].starts_with("<![CDATA[") {
match code[i + 9..].find("]]>") {
Some(n) => {
i += n + 11;
}
None => {
return false;
}
};
} else if code[i..].starts_with("</") {
let j = i + 2;
match code[j..].find('>') {
Some(n) => {
let t = &code[j..j + n];
if !check(t) || stk.is_empty() || stk.pop().unwrap() != t {
return false;
}
i += n + 2;
}
None => {
return false;
}
};
} else if code[i..].starts_with("<") {
let j = i + 1;
match code[j..].find('>') {
Some(n) => {
let t = &code[j..j + n];
if !check(t) {
return false;
}
stk.push(t);
}
None => {
return false;
}
};
}
i += 1;
}
stk.is_empty()
}
}
|
