Tag Validator — LeetCode 591 Python Solution
HardStackString
- Problem
- #591
- Pattern
- Stack
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
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>.
Python solution
Python
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 stkComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 591. Tag Validator is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 591. Tag Validator?
- LeetCode 591. Tag Validator is rated Hard on LeetCode.
- What is the time complexity of LeetCode 591. Tag Validator?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 591. Tag Validator?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 591. Tag Validator cover?
- LeetCode 591. Tag Validator is tagged Stack and String on LeetCode.