]]>
```
is still valid CDATA.
The parser should skip directly to the closing `]]>`.
Important rule:
CDATA is only allowed inside an open tag.
So:
```text
```
alone is invalid.
## Algorithm
Use a stack and scan the string with index `i`.
While `i < len(code)`:
1. If we see ``.
- If missing, return `False`.
- Skip the entire CDATA section.
2. Else if we see ``.
- Extract the tag name.
- Validate the tag name.
- The stack top must match.
- Pop the stack.
- If the stack becomes empty before the end of the string, return `False`.
3. Else if we see `<`:
- Find the next `>`.
- Extract the tag name.
- Validate the tag name.
- Push the tag name onto the stack.
4. Else:
- Normal text is allowed only inside an open tag.
- If the stack is empty, return `False`.
At the end, return whether the stack is empty.
## Correctness
The stack always stores exactly the currently open tags that have not yet been closed.
When a valid start tag is encountered, its tag name is pushed onto the stack. Therefore, the stack correctly tracks nesting depth.
When an end tag is encountered, the algorithm checks whether the tag name matches the top of the stack. If it does not match, the nesting structure is invalid, so returning `False` is correct. If it matches, popping the stack correctly closes that tag.
CDATA sections are skipped entirely between ``, so any characters inside CDATA are ignored exactly as required by the problem statement.
Text outside tags is only allowed when some tag is currently open. Therefore, if the stack is empty while processing plain text, the code is invalid.
The requirement that the entire string must be wrapped in exactly one root tag is enforced by checking that once the stack becomes empty, the parser must already be at the end of the string.
At the end of parsing, the stack is empty exactly when every opened tag has been properly closed.
Therefore, the algorithm returns `True` exactly for valid code snippets.
## Complexity
Let:
```text
n = len(code)
```
| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each character is processed at most a constant number of times |
| Space | `O(n)` | The stack may contain nested tags |
## Implementation
```python
class Solution:
def isValid(self, code: str) -> bool:
stack = []
n = len(code)
i = 0
while i < n:
if i > 0 and not stack:
return False
if code.startswith("", i)
if j == -1:
return False
i = j + 3
elif code.startswith("", i)
if j == -1:
return False
tag = code[i + 2:j]
if (
len(tag) < 1
or len(tag) > 9
or not tag.isupper()
or not tag.isalpha()
):
return False
if not stack or stack[-1] != tag:
return False
stack.pop()
i = j + 1
elif code[i] == "<":
j = code.find(">", i)
if j == -1:
return False
tag = code[i + 1:j]
if (
len(tag) < 1
or len(tag) > 9
or not tag.isupper()
or not tag.isalpha()
):
return False
stack.append(tag)
i = j + 1
else:
if not stack:
return False
i += 1
return not stack
```
## Code Explanation
The stack stores currently open tags:
```python
stack = []
```
This rule enforces one outer root tag:
```python
if i > 0 and not stack:
return False
```
If the stack becomes empty before the end of the string, extra content exists outside the root tag.
CDATA detection:
```python
if code.startswith("`:
```python
j = code.find("]]>", i)
```
End tag parsing:
```python
elif code.startswith(" 9
or not tag.isupper()
or not tag.isalpha()
```
Then the top stack tag must match:
```python
if not stack or stack[-1] != tag:
return False
```
Start tags work similarly:
```python
elif code[i] == "<":
```
Valid tags are pushed:
```python
stack.append(tag)
```
Finally:
```python
return not stack
```
All tags must be properly closed.
## Testing
```python
def run_tests():
s = Solution()
assert s.isValid(
"This is the first line ]]>
"
) is True
assert s.isValid(
">> ![cdata[]] ]>]]>]]>>]
"
) is True
assert s.isValid(
" "
) is False
assert s.isValid(
""
) is True
assert s.isValid(
"