591. Tag Validator
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_NAMEonly contain upper-case letters, and has length in range [1,9]. Otherwise, theTAG_NAMEis invalid. - A valid
TAG_CONTENTmay 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, theTAG_CONTENTis 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 ofCDATA_CONTENTis defined as the characters between<![CDATA[and the first subsequent]]>. CDATA_CONTENTmay contain any characters. The function of cdata is to forbid the validator to parseCDATA_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 <= 500codeconsists of English letters, digits,'<','>','/','!','[',']','.', and' '.
Solutions
Solution 1
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
Rust
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()
}
}