Watch 6 video solutions for Tag Validator, a hard level problem involving String, Stack. This walkthrough by Huifeng Guan has 669 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
<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.TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.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.< 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).<![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 ' '.Problem Overview: You are given a string representing code written with XML‑style tags. A valid code snippet must follow strict rules: tags must be uppercase, properly nested, wrapped by a single root tag, and CDATA sections must be ignored during validation. The task is to check whether the entire string forms a valid tagged structure.
Approach 1: Stack-Based Parsing (O(n) time, O(n) space)
This approach simulates how a real parser validates nested tags. Iterate through the string character by character. When you encounter an opening tag like <TAG>, push the tag name onto a stack. When a closing tag like </TAG> appears, verify that it matches the stack's top element and pop it. If the order breaks or a closing tag appears without a corresponding opening tag, the code is invalid.
CDATA blocks such as <![CDATA[...]]> require special handling. Once detected, skip all characters until the closing ]]> because content inside CDATA should not be parsed as tags. Tag names must be between 1 and 9 uppercase letters, which you validate while parsing. At the end, the stack must be empty and the entire string must be enclosed by one root tag. This approach runs in O(n) time because each character is processed once, with O(n) space for the stack in the worst case. It relies heavily on concepts from stack processing and string parsing.
Approach 2: Regex-Based Validation (O(n)–O(n²) time, O(n) space)
A regex-driven strategy repeatedly simplifies the string until only a valid root tag remains. First replace CDATA sections using a pattern that matches <![CDATA[...]]> so the parser ignores their internal content. Next apply a regex that matches valid tag structures such as <TAG>content</TAG>. Each successful match can be replaced with a placeholder character.
By repeatedly applying this replacement, nested tags collapse layer by layer. If the final string reduces to a single placeholder representing the root element, the code is valid. While this technique is concise and expressive in languages with strong regex support, repeated replacements may re-scan the string multiple times. That pushes the practical complexity closer to O(n²) in worst cases. It works well for quick validation scripts but is less predictable for large inputs.
Recommended for interviews: The stack-based parser is the expected solution. It demonstrates clear reasoning about nested structures, explicit state management, and careful handling of edge cases like CDATA and tag length rules. Regex-based solutions can work but often hide logic inside complex patterns and repeated replacements. Showing the stack approach proves you understand parsing fundamentals and data structure design.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Parsing | O(n) | O(n) | Best general solution for interviews and production parsers |
| Regex-Based Validation | O(n)–O(n²) | O(n) | Quick validation scripts where concise regex is preferred |