Tag Validator
HardPrompt
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' '.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach attempts to validate the code by repeatedly simplifying it. It uses regular expressions to find and replace valid, innermost structures like CDATA sections and leaf tags (tags with no nested tags). The process continues until no more simplifications can be made. If the code reduces to a valid state, it's considered valid.
Algorithm
- First, perform a preliminary check to see if the code is wrapped by a matching start and end tag. A simple way is to use a regular expression like
^<([A-Z]{1,9})>(.*)</\1>$. - If this check fails, the code is invalid. Otherwise, extract the content between the outermost tags.
- Enter a
whileloop that continues as long as the content string is being simplified in an iteration. - Inside the loop, store the length of the content string before any modifications.
- Use
String.replaceAll()to replace all occurrences of the CDATA pattern<!\[CDATA\[.*?\]\]>with a placeholder or an empty string. The.*?is crucial for a non-greedy match to respect the "first subsequent]]>" rule. - Use
String.replaceAll()to replace all occurrences of the leaf tag pattern<([A-Z]{1,9})>[^<]*</\1>with a placeholder or an empty string.[^<]*ensures the tag content has no other nested tags. - After the replacements, if the content's length has not changed, break the loop as no more simplifications are possible.
- After the loop terminates, the original code is considered valid if the content string has been reduced to an empty string.
Walkthrough
The core idea is to iteratively reduce the code string by removing valid, self-contained parts. If the entire string can be successfully reduced, it's deemed valid.
We can define regular expressions for the constructs we need to parse: CDATA sections and valid tags with simple text content. We repeatedly apply these regexes to remove these parts from the code. For this to work correctly, we must first ensure the code is wrapped in a single root tag, and then apply the reductions only to the content within that root tag.
For example, in <A><B></B></A>, the inner <B></B> would be removed first, leaving <A></A>. Then, <A></A> would be removed, leaving an empty string, indicating success.
class Solution { public boolean isValid(String code) { // This regex-based approach is primarily for demonstration and is not fully robust. // It's inefficient and can fail on complex nested cases. String tempCode = code; String prevCode; // Repeatedly remove CDATA and innermost valid tags. do { prevCode = tempCode; // Replace CDATA sections with a placeholder 'c'. tempCode = prevCode.replaceAll("<!\[CDATA\[.*?\]\]>", "c"); // Replace valid leaf tags (no nested tags) with a placeholder 't'. tempCode = tempCode.replaceAll("<([A-Z]{1,9})>[^<]*</\\1>", "t"); } while (tempCode.length() < prevCode.length()); // A valid code block should reduce to a single placeholder 't'. // This simplified check fails for cases like `<A></A><B></B>` which would become "tt". // A more robust implementation is significantly more complex. return tempCode.equals("t"); }}Complexity
Time
O(D * N^2), where N is the length of the code and D is the maximum nesting depth. Each `replaceAll` operation can take O(N^2) time in the worst case (pattern matching and new string construction), and the loop can run up to D times.
Space
O(N), where N is the length of the code. Each call to `replaceAll` can create a new string of length proportional to N.
Trade-offs
Pros
Conceptually simple for basic cases, relying on the power of regex for pattern matching.
Can lead to very concise code if the language's regex engine is powerful enough.
Cons
Very inefficient due to repeated string manipulations and pattern matching on potentially large strings. In Java,
Stringis immutable, so each replacement creates a new string.Regular expressions are not well-suited for parsing recursively nested structures. It's extremely difficult to formulate a regex that is both correct and robust for all the edge cases specified in the problem.
High risk of subtle bugs due to regex complexities, such as greediness, and correctly handling all validation rules simultaneously.
This is the standard and most efficient way to solve problems involving nested, balanced structures, like parentheses or XML/HTML tags. We iterate through the code string once, using a stack to keep track of the open tags. This allows us to enforce the proper nesting and matching rules in a single pass.
Algorithm
- Initialize an empty
Stack<String>to store tag names. - Iterate through the
codestring with an indexi. - If the current character
code.charAt(i)is not<:- It's text content. This is only valid if the stack is not empty (i.e., we are inside a tag). If the stack is empty, return
false.
- It's text content. This is only valid if the stack is not empty (i.e., we are inside a tag). If the stack is empty, return
- If the current character is
<:- Check if it's a CDATA section (
<![CDATA[...]]>). If so, validate that the stack is not empty, find the closing]]>, and advanceipast it. If any part fails, returnfalse. - Check if it's an end tag (
</TAG_NAME>). If so, extract theTAG_NAME. Check if the stack is empty or if the popped tag name from the stack doesn't match. If either is true, returnfalse. Also, if the stack becomes empty after popping, we must be at the end of the string; otherwise, it implies multiple root tags, so returnfalse. - Otherwise, it's a start tag (
<TAG_NAME>). Extract and validate theTAG_NAME(1-9 uppercase letters). If valid, push it onto the stack. - Advance
ipast the entire tag or CDATA block.
- Check if it's a CDATA section (
- After the loop finishes, the code is valid if and only if the stack is empty.
Walkthrough
We treat the problem as a parsing task. A stack is the perfect data structure to manage the hierarchy of open tags. The Last-In, First-Out (LIFO) nature of a stack naturally corresponds to the rule that the most recently opened tag must be the first one to be closed.
The algorithm proceeds with a single pass over the input string. It maintains a stack of tag names. When a start tag is encountered, its name is pushed onto the stack. When an end tag is found, we check if it matches the tag name at the top of the stack. If it does, we pop the stack, signifying that the tag has been correctly closed. Special care is taken for CDATA sections, which are treated as plain text and skipped over. The overall validity is determined by whether the stack is empty at the very end of the string, ensuring all tags were properly closed.
import java.util.Stack; class Solution { public boolean isValid(String code) { Stack<String> stack = new Stack<>(); int i = 0; while (i < code.length()) { if (code.charAt(i) != '<') { if (stack.isEmpty()) { return false; // Content outside of any tag } i++; continue; } if (i == code.length() - 1) return false; // Unclosed '<' at the end if (code.charAt(i + 1) == '/') { // End tag int j = code.indexOf('>', i + 2); if (j == -1) return false; // Unclosed end tag String tagName = code.substring(i + 2, j); if (stack.isEmpty() || !stack.pop().equals(tagName)) { return false; // Mismatched or unexpected end tag } i = j + 1; if (stack.isEmpty() && i < code.length()) { return false; // Content after the root tag closes } } else if (code.charAt(i + 1) == '!') { // CDATA if (stack.isEmpty() || i + 9 > code.length() || !code.substring(i, i + 9).equals("<![CDATA[")) { return false; // CDATA must be inside a tag and have correct prefix } int j = code.indexOf("]]\>", i + 9); if (j == -1) return false; // Unclosed CDATA i = j + 3; } else { // Start tag int j = code.indexOf('>', i + 1); if (j == -1) return false; // Unclosed start tag String tagName = code.substring(i + 1, j); if (!isValidTagName(tagName)) { return false; } stack.push(tagName); i = j + 1; } } return stack.isEmpty(); } private boolean isValidTagName(String name) { if (name.length() < 1 || name.length() > 9) { return false; } for (char c : name.toCharArray()) { if (!Character.isUpperCase(c)) { return false; } } return true; }}Complexity
Time
O(N), where N is the length of the `code` string. We iterate through the string once. Operations like `indexOf` and `substring` are used, but the main index `i` is always advanced past the processed segment, ensuring each character is examined a constant number of times in total.
Space
O(D), where D is the maximum nesting depth of the tags. In the worst-case scenario of fully nested tags (`<A><B><C>...</C></B></A>`), D can be proportional to N, making the space complexity O(N). This space is used by the stack.
Trade-offs
Pros
Highly efficient with a single-pass linear time complexity.
Correctly and robustly handles all specified rules, including deeply nested structures and edge cases.
It is the standard, idiomatic solution for this class of parsing problems, making it maintainable and easy to understand for developers familiar with stack-based algorithms.
Cons
The implementation logic is more involved than a naive approach, requiring careful management of the parsing index
iand handling multiple distinct cases (start tag, end tag, CDATA, text).
Solutions
Solution
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; }}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; }};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 stkVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.