Tag Validator
Hard · Stack & Strings · String · Stack
Problem
You are given a string code containing a code snippet. Return true if the snippet is valid and false otherwise. A snippet is valid when all of these rules hold:
- The whole snippet is wrapped in one valid closed tag.
- A closed tag has the form TAG_CONTENT, where the start and end tags use the same name. It is valid only if its TAG_NAME and TAG_CONTENT are both valid.
- A valid TAG_NAME consists only of uppercase letters and is between 1 and 9 characters long.
- Valid TAG_CONTENT may contain other valid closed tags, CDATA sections and arbitrary characters, but it must not contain an unmatched follows it. When you meet is read as the tag name, whether or not that name is valid.
- A CDATA section has the form , where the content runs from after it. Its content is never parsed, so it may contain anything, including text that looks like tags.
Examples
Input: code = "<B><![CDATA[</B>]]>ok</B>" Output: true
The inside the CDATA section is ignored, so the outer B closes at the end.
Input: code = "<A></A><B></B>" Output: false
The snippet is two sibling tags rather than one wrapping tag.
Input: code = "<AB>x</ab>" Output: false
The end tag name is lowercase and does not match AB.
Constraints
- 1 <= len(code) <= 500
- code consists of English letters, digits, '', '/', '!', '[', ']', '.' and ' '
Approaches
- Collapse innermost tags until one is left — time O(n²), space O(n)
Follow-up
The order of the checks matters: <