591. Tag Validator LeetCode Solution
In this guide, you will get 591. Tag Validator LeetCode Solution with the best time and space complexity. The solution to Tag Validator problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Tag Validator solution in C++
- Tag Validator solution in Java
- Tag Validator solution in Python
- Additional Resources
Problem Statement of Tag Validator
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_CONTENT. Among them, is the start tag, and 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 . And when you find a < or should be parsed as TAG_NAME (not necessarily valid).
The cdata has the following format : . The range of CDATA_CONTENT is defined as the characters between .
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 = “
Output: true
Explanation:
The code is wrapped in a closed tag :
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 = “
Output: true
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -> “
end_tag -> “
tag_content could also be separated into : text1|cdata|text2.
text1 -> “>> ![cdata[]] ”
cdata -> “<![CDATA[
text2 -> “]]>>]”
The reason why start_tag is NOT “
The reason why cdata is NOT “<![CDATA[
Example 3:
Input: code = “ ”
Output: false
Explanation: Unbalanced. If “” is closed, then “” must be unmatched, and vice versa.
Constraints:
1 <= code.length <= 500
code consists of English letters, digits, '’, ‘/’, ‘!’, ‘[‘, ‘]’, ‘.’, and ‘ ‘.
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
591. Tag Validator LeetCode Solution in C++
class Solution {
public:
bool isValid(string code) {
if (code[0] != '<' || code.back() != '>')
return false;
stack<string> stack;
for (int i = 0; i < code.length(); ++i) {
int closeIndex = 0;
if (stack.empty() && containsTag)
return false;
if (code[i] == '<') {
// It's inside a tag, so check if it's a cdata.
if (!stack.empty() && code[i + 1] == '!') {
closeIndex = code.find("]]>", i + 2);
if (closeIndex == string::npos ||
!isValidCdata(code.substr(i + 2, closeIndex - i - 2)))
return false;
} else if (code[i + 1] == '/') { // the end tag
closeIndex = code.find('>', i + 2);
if (closeIndex == string::npos ||
!isValidTagName(stack, code.substr(i + 2, closeIndex - i - 2),
true))
return false;
} else { // the start tag
closeIndex = code.find('>', i + 1);
if (closeIndex == string::npos ||
!isValidTagName(stack, code.substr(i + 1, closeIndex - i - 1),
false))
return false;
}
i = closeIndex;
}
}
return stack.empty() && containsTag;
}
private:
bool containsTag = false;
bool isValidCdata(const string& s) {
return s.find("[CDATA[") == 0;
}
bool isValidTagName(stack<string>& stack, const string& tagName,
bool isEndTag) {
if (tagName.empty() || tagName.length() > 9)
return false;
for (const char c : tagName)
if (!isupper(c))
return false;
if (isEndTag) {
if (stack.empty())
return false;
if (stack.top() != tagName)
return false;
stack.pop();
return true;
}
containsTag = true;
stack.push(tagName);
return true;
}
};
/* code provided by PROGIEZ */591. Tag Validator LeetCode Solution in Java
class Solution {
public boolean isValid(String code) {
if (code.charAt(0) != '<' || code.charAt(code.length() - 1) != '>')
return false;
Deque<String> stack = new ArrayDeque<>();
for (int i = 0; i < code.length(); ++i) {
int closeIndex = 0;
if (stack.isEmpty() && containsTag)
return false;
if (code.charAt(i) == '<') {
// It's inside a tag, so check if it's a cdata.
if (!stack.isEmpty() && code.charAt(i + 1) == '!') {
closeIndex = code.indexOf("]]>", i + 2);
if (closeIndex < 0 || !isValidCdata(code.substring(i + 2, closeIndex)))
return false;
} else if (code.charAt(i + 1) == '/') { // the end tag
closeIndex = code.indexOf('>', i + 2);
if (closeIndex < 0 || !isValidTagName(stack, code.substring(i + 2, closeIndex), true))
return false;
} else { // the start tag
closeIndex = code.indexOf('>', i + 1);
if (closeIndex < 0 || !isValidTagName(stack, code.substring(i + 1, closeIndex), false))
return false;
}
i = closeIndex;
}
}
return stack.isEmpty() && containsTag;
}
private boolean containsTag = false;
private boolean isValidCdata(final String s) {
return s.indexOf("[CDATA[") == 0;
}
private boolean isValidTagName(Deque<String> stack, String tagName, boolean isEndTag) {
if (tagName.isEmpty() || tagName.length() > 9)
return false;
for (final char c : tagName.toCharArray())
if (!Character.isUpperCase(c))
return false;
if (isEndTag)
return !stack.isEmpty() && stack.pop().equals(tagName);
containsTag = true;
stack.push(tagName);
return true;
}
}
// code provided by PROGIEZ591. Tag Validator LeetCode Solution in Python
class Solution:
def isValid(self, code: str) -> bool:
if code[0] != '<' or code[-1] != '>':
return False
containsTag = False
stack = []
def isValidCdata(s: str) -> bool:
return s.find('[CDATA[') == 0
def isValidTagName(tagName: str, isEndTag: bool) -> bool:
nonlocal containsTag
if not tagName or len(tagName) > 9:
return False
if any(not c.isupper() for c in tagName):
return False
if isEndTag:
return stack and stack.pop() == tagName
containsTag = True
stack.append(tagName)
return True
i = 0
while i < len(code):
if not stack and containsTag:
return False
if code[i] == '<':
# It's inside a tag, so check if it's a cdata.
if stack and code[i + 1] == '!':
closeIndex = code.find(']]>', i + 2)
if closeIndex == -1 or not isValidCdata(code[i + 2:closeIndex]):
return False
elif code[i + 1] == '/': # the end tag
closeIndex = code.find('>', i + 2)
if closeIndex == -1 or not isValidTagName(
code[i + 2: closeIndex],
True):
return False
else: # the start tag
closeIndex = code.find('>', i + 1)
if closeIndex == -1 or not isValidTagName(
code[i + 1: closeIndex],
False):
return False
i = closeIndex
i += 1
return not stack and containsTag
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.