Leetcode #591: Tag Validator
In this guide, we solve Leetcode #591 Tag Validator in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Stack, String
Intuition
The problem has a natural nested or last-in-first-out structure.
A stack lets us resolve matches in the correct order as we scan.
Approach
Push items as they appear and pop when you can finalize a decision.
The stack captures the unresolved part of the input.
Steps:
- Push elements as you scan.
- Pop when a rule or match is satisfied.
- Use the stack to compute results.
Example
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.
Python Solution
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 stk
Complexity
The time complexity is O(n). The space complexity is O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.