Formatted question description: https://leetcode.ca/all/591.html
591. Tag Validator (Hard)
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:
- 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, theTAG_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, theTAG_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 ofCDATA_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 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.
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:
- For simplicity, you could assume the input code (including the any characters mentioned above) only contain
letters
,digits
,'<'
,'>'
,'/'
,'!'
,'['
,']'
and' '
.
Solution 1. Automaton
I did similar job before, so the first thing came into my mind is automaton. Maybe it’s not neat, but the tasks in each state is quite clear.
// OJ: https://leetcode.com/problems/tag-validator
// Time: O(N)
// Space: O(H)
class Solution {
private:
enum State {
INIT,
START_TAG,
TAG_CONTENT,
END_TAG,
CDATA
};
public:
bool isValid(string code) {
stack<string> s;
State state = INIT;
string startTag, endTag;
int i = 0;
while (i < code.size()) {
switch(state) {
case INIT: {
if (code[i] != '<') return false;
++i; // <
state = START_TAG;
break;
}
case START_TAG: {
while (i < code.size() && isupper(code[i])) {
startTag += code[i++];
}
if (i >= code.size() || code[i] != '>' || startTag.empty() || startTag.size() > 9) return false;
s.push(startTag);
++i; // >
state = TAG_CONTENT;
break;
}
case TAG_CONTENT: {
while (i < code.size() && code[i] != '<') ++i;
if (i >= code.size() || code[i] != '<') return false;
++i; // <
if (i < code.size() && code[i] == '/') {
++i; // /
state = END_TAG;
endTag.clear();
} else if (i < code.size() && code[i] == '!') {// <![CDATA[
string mark = "![CDATA[";
int j = 0;
while (i < code.size() && j < mark.size() && code[i] == mark[j]) ++i, ++j;
if (j < mark.size()) return false;
state = CDATA;
} else {
state = START_TAG;
startTag.clear();
}
break;
}
case END_TAG: {
while (i < code.size() && isupper(code[i])) {
endTag += code[i++];
}
if (i >= code.size() || code[i] != '>' || endTag.empty() || s.empty() || s.top() != endTag) return false;
s.pop();
++i; // >
if (s.empty() && i < code.size()) return false;
state = TAG_CONTENT;
break;
}
case CDATA: {
int end = code.find("]]>", i);
if (end == string::npos) return false;
i = end + 3;
state = TAG_CONTENT;
break;
}
}
}
return s.empty();
}
};
Java
-
public class Solution { public boolean isValid(String code) { if (code == null || code.length() == 0) return false; Stack<String> stack = new Stack<String>(); int length = code.length(); int index = 0; while (index < length) { if (index > 0 && stack.isEmpty()) return false; if (index + 9 <= length && code.substring(index, index + 9).equals("<![CDATA[")) { index += 9; while (index <= length - 3 && !code.substring(index, index + 3).equals("]]>")) index++; if (index > length - 3) return false; else index += 2; } else if (code.substring(index, index + 2).equals("</")) { index += 2; int start = index; while (index < length && code.charAt(index) != '>') index++; if (index >= length) return false; String tag = code.substring(start, index); if (stack.isEmpty() || !stack.peek().equals(tag)) return false; stack.pop(); } else if (code.charAt(index) == '<') { index++; int start = index; while (index < length && code.charAt(index) != '>') index++; if (index >= length || index == start || index - start > 9) return false; for (int i = start; i < index; i++) { char c = code.charAt(i); if (c < 'A' || c > 'Z') return false; } String tag = code.substring(start, index); stack.push(tag); } index++; } return stack.isEmpty(); } }
-
// OJ: https://leetcode.com/problems/tag-validator // Time: O(N) // Space: O(H) class Solution { private: enum State { INIT, START_TAG, TAG_CONTENT, END_TAG, CDATA }; public: bool isValid(string code) { stack<string> s; State state = INIT; string startTag, endTag; int i = 0; while (i < code.size()) { switch(state) { case INIT: { if (code[i] != '<') return false; ++i; // < state = START_TAG; break; } case START_TAG: { while (i < code.size() && isupper(code[i])) { startTag += code[i++]; } if (i >= code.size() || code[i] != '>' || startTag.empty() || startTag.size() > 9) return false; s.push(startTag); ++i; // > state = TAG_CONTENT; break; } case TAG_CONTENT: { while (i < code.size() && code[i] != '<') ++i; if (i >= code.size() || code[i] != '<') return false; ++i; // < if (i < code.size() && code[i] == '/') { ++i; // / state = END_TAG; endTag.clear(); } else if (i < code.size() && code[i] == '!') {// <![CDATA[ string mark = "![CDATA["; int j = 0; while (i < code.size() && j < mark.size() && code[i] == mark[j]) ++i, ++j; if (j < mark.size()) return false; state = CDATA; } else { state = START_TAG; startTag.clear(); } break; } case END_TAG: { while (i < code.size() && isupper(code[i])) { endTag += code[i++]; } if (i >= code.size() || code[i] != '>' || endTag.empty() || s.empty() || s.top() != endTag) return false; s.pop(); ++i; // > if (s.empty() && i < code.size()) return false; state = TAG_CONTENT; break; } case CDATA: { int end = code.find("]]>", i); if (end == string::npos) return false; i = end + 3; state = TAG_CONTENT; break; } } } return s.empty(); } };
-
import string class Solution(object): def isValid(self, code): """ :type code: str :rtype: bool """ def getTokenStartsAt(start): for i in range(start, len(code)): if code[i] == ">": break return code[start:i + 1] def isTagsMatched(left, right): return len(left) + 1 == len(right) and left[1:] == right[2:] def isClosedTag(tag): return tag[1] == "/" def isCDATATag(i): return code.startswith("<![CDATA[", i) def isTag(tag): if len(tag) < 3: return False if tag[-1] != ">": return False tag = tag[1:-1] if tag[0] == "/": tag = tag[1:] if not 1 <= len(tag) <= 9: return False for c in tag: if c not in string.ascii_uppercase: return False return True if code[0] != "<": return False tagLen = 0 stack = [] i = 0 while i < len(code): if code[i] == "<": if isCDATATag(i): if not stack: return False while i < len(code) - 7 and not code.startswith("]]>", i): i += 1 if code.startswith("]]>", i): i += 3 continue else: return False else: token = getTokenStartsAt(i) if not isTag(token): return False if not isClosedTag(token): stack.append(token) else: if not stack: return False if isTagsMatched(stack[-1], token): stack.pop() if not stack and i + len(token) < len(code): return False else: return False i += len(token) else: i += 1 return not stack