LeetCode 591: Tag Validator Solution in Python – A Step-by-Step Guide
Imagine you’re tasked with checking if a snippet of code—like "This is a test"—follows the rules of a simple HTML-like tagging system, ensuring tags open and close correctly, such as validating it as true, while rejecting "unclosed" as false. That’s the intriguing challenge of LeetCode 591: Tag Validator, a hard-level problem that’s a fantastic way to practice string parsing in Python. We’ll explore two solutions: the Best Solution, a stack-based parsing approach that’s efficient and clear, and an Alternative Solution, a recursive parsing method that’s thorough but more complex. With detailed examples, clear code, and a friendly tone—especially for the stack approach—this guide will help you validate those tags, whether you’re new to coding or leveling up. Let’s parse that code and start validating!
What Is LeetCode 591: Tag Validator?
In LeetCode 591: Tag Validator, you’re given a string code representing a snippet of HTML-like markup, and your task is to return True if it’s a valid tag sequence and False otherwise. A valid sequence must follow these rules: tags are uppercase, 1-9 characters long (e.g., , ), must close in matching pairs (e.g., ), and content between tags must be valid (plain text, CDATA, or nested tags). For example, code = "
Problem Statement
- Input: code (str)—HTML-like tag sequence.
- Output: Boolean—True if valid, False otherwise.
- Rules:
- Tags: <tag_name></tag_name> where TAG_NAME is 1-9 uppercase letters.
- Closing: <tag_name></tag_name> must pair with.
- Content: Plain text, CDATA (...), or nested valid tags.
- No < or > within plain text unless part of tags/CDATA.
Constraints
- 1 <= code.length <= 5 * 10⁴
- code contains uppercase letters, lowercase letters, digits, <, >, /, [, ], !, and text.
Examples
- Input: code = "This is a test"
- Output: True
- Valid: opens, closes with , text content allowed.
- Input: code = "unclosed"
- Output: False
- Missing closing tag .
- Input: code = "<test>"
- Output: True
- CDATA allows < and > inside, valid with matching tags.
Best Solution: Stack-Based Parsing
Why Stack Wins
The stack-based parsing solution is the best for LeetCode 591 because it validates the tag sequence in O(n) time and O(n) space by using a stack to track opening tags, parsing the string character-by-character with a pointer, and efficiently handling nested tags and CDATA sections in a single pass. It’s like reading a book, keeping a bookmark stack of where each chapter starts, and checking they close properly—all in a swift, organized read!
How It Works
Think of this as a tag-checking librarian:
- Step 1: Initialize Stack and Pointer:
- Stack for opening tags, pointer i at 0.
- Step 2: Parse String:
- If < found:
- Check for closing tag , validate against stack top.
- Check for CDATA , skip to end ]]>.
- Otherwise, parse opening tag, push to stack.
- Move pointer past tag/content.
- Step 3: Validate Tag Name:
- 1-9 uppercase letters between < and >.
- Step 4: Check Completion:
- Stack empty at end = valid.
- Why It Works:
- Stack ensures matching tags in correct order.
- Linear scan handles complexity efficiently.
It’s like a tag-validation maestro!
Step-by-Step Example
Example: code = "This is a test"
- Init: Stack = [], i = 0.
- Step 1: i = 0, :
- Valid tag "DIV" (3 uppercase), push "DIV", Stack = ["DIV"], i = 5.
- Step 2: i = 5, "This is a test", skip text, i = 19.
- Step 3: i = 19, :
- Closing tag "DIV", pop Stack top "DIV", match, Stack = [], i = 25.
- Step 4: End, Stack empty, valid.
- Result: True.
Example: code = "<![CDATA[<test>]]></test>"
- Step 1: i = 0, :
- Push "DIV", Stack = ["DIV"], i = 5.
- Step 2: i = 5, <test>:
- CDATA, skip to ]]>, i = 22.
- Step 3: i = 22, :
- Pop "DIV", match, Stack = [], i = 28.
- Step 4: End, Stack empty, valid.
- Result: True.
Code with Detailed Line-by-Line Explanation
Here’s the Python code, explained for beginners:
class Solution:
def isValid(self, code: str) -> bool:
stack = []
i = 0
n = len(code)
while i < n:
if code[i] != '<':
# Must be within tags or CDATA
if not stack:
return False
i += 1
continue
# Step 1: Handle closing tag
if i + 1 < n and code[i + 1] == '/':
if not stack:
return False
j = code.find('>', i)
if j == -1:
return False
tag = code[i + 2:j]
if not self._is_valid_tag(tag) or stack[-1] != tag:
return False
stack.pop()
i = j + 1
# Must have processed entire string if stack empty
if not stack and i < n:
return False
continue
# Step 2: Handle CDATA
if i + 8 < n and code[i:i + 9] == '<![CDATA[':
if not stack:
return False
j = code.find(']]>', i)
if j == -1:
return False
i = j + 3
continue
# Step 3: Handle opening tag
j = code.find('>', i)
if j == -1:
return False
tag = code[i + 1:j]
if not self._is_valid_tag(tag):
return False
stack.append(tag)
i = j + 1
# Step 4: Check if all tags closed
return len(stack) == 0
def _is_valid_tag(self, tag: str) -> bool:
# Tag must be 1-9 uppercase letters
return 1 <= len(tag) <= 9 and all(c.isupper() for c in tag)- Lines 3-6: Initialize stack and pointer.
- Lines 8-12: Skip non-tag characters, invalid if outside tags.
- Lines 15-27: Closing tag:
- Check , match with stack top, pop if valid.
- Lines 30-37: CDATA:
- Skip to ]]>, invalid if outside tags.
- Lines 40-47: Opening tag:
- Parse <tag></tag>, validate, push to stack.
- Line 50: Return True if stack empty (all tags closed).
- Lines 53-55: Helper: Check tag is 1-9 uppercase letters.
- Time Complexity: O(n)—single pass through string.
- Space Complexity: O(n)—stack for nested tags.
It’s like a tag-parsing wizard!
Alternative Solution: Recursive Parsing
Why an Alternative Approach?
The recursive parsing approach breaks the string into segments, validating each recursively, running in O(n) time and O(n) space due to recursion depth. It’s thorough but more complex, making it a good alternative for understanding or when stack space isn’t a concern.
How It Works
Picture this as a recursive tag explorer:
- Step 1: Define recursive function with start index.
- Step 2: Base case: Empty or no tags left.
- Step 3: Find tags, validate, recurse on content.
- Step 4: Return validity.
It’s like a recursive tag checker!
Step-by-Step Example
Example: code = "text"
- Step 1: Start at 0:
- Step 2: Return True.
- Result: True.
Code for Recursive Approach
class Solution:
def isValid(self, code: str) -> bool:
def parse(i: int, n: int) -> Tuple[bool, int]:
if i >= n:
return True, i
if code[i] != '<':
return False, i
j = code.find('>', i)
if j == -1 or not self._is_valid_tag(code[i + 1:j]):
return False, i
tag = code[i + 1:j]
i = j + 1
while i < n and code[i] != '<':
i += 1
if i >= n:
return False, i
if code[i:i + 2] == '</':
k = code.find('>', i)
if k == -1 or code[i + 2:k] != tag:
return False, i
return True, k + 1
return parse(i, n)
def _is_valid_tag(self, tag: str) -> bool:
return 1 <= len(tag) <= 9 and all(c.isupper() for c in tag)
valid, end = parse(0, len(code))
return valid and end == len(code)- Lines 4-24: Recursive parse:
- Validate opening tag, recurse on content, match closing tag.
- Lines 27-28: Tag validation helper.
- Line 31: Check full string processed.
- Time Complexity: O(n)—linear with recursion.
- Space Complexity: O(n)—recursion stack.
It’s a recursive tag validator!
Comparing the Two Solutions
- Stack (Best):
- Pros: O(n), O(n), clear and efficient.
- Cons: Stack space for nesting.
- Recursive (Alternative):
- Pros: O(n), O(n), thorough.
- Cons: More complex logic.
Stack wins for clarity!
Additional Examples and Edge Cases
- Empty string: False.
- Single tag: Valid if closed.
- Nested tags: Must match.
Stack handles them all!
Complexity Recap
- Stack: Time O(n), Space O(n).
- Recursive: Time O(n), Space O(n).
Stack’s the efficiency champ!
Key Takeaways
- Stack: Parsing finesse—learn at Python Basics!
- Recursive: Deep dive.
- Tags: Validation is fun.
- Python: Stack or recurse, your pick!