Valid Nested Tags ā Problem Statement & Solution Guide
Problem Description
Given a sequence of tags, determine whether the sequence is valid, meaning every opening tag can be matched with a corresponding closing tag. The sequence is valid if it is possible to pair every opening tag with a closing tag that occurs after it, and the tags are properly nested.
Examples
Input
<a><b></b></a>
Output
true
Explanation: Step-by-step: 1. Initialize an empty stack. 2. Iterate through the input string. When '<' is encountered, push the tag name to the stack. When '</' is encountered, check if the stack is empty or the top of the stack does not match the closing tag. If either condition is true, return false. If the stack is empty after iterating through the entire string, return true.
Input
<a><b></a></b>
Output
false
Explanation: Step-by-step: 1. Initialize an empty stack. 2. Iterate through the input string. When '<' is encountered, push the tag name to the stack. When '</' is encountered, check if the stack is empty or the top of the stack does not match the closing tag. If either condition is true, return false. If the stack is empty after iterating through the entire string, return true.
Constraints
- The input sequence will contain at most 1000 tags.
- The input sequence will only contain valid XML tag names and '<' and '>' characters.
Optimal Approach & Strategy
The optimal approach is to use a stack data structure to parse the XML sequence. This approach has a time complexity of O(n) as we make a single pass through the input string, and a space complexity of O(n) for storing the opening tags in the stack.
Brute Force Approach
One naive approach would be to generate all possible valid XML sequences and check if the given sequence matches any of them. This would have a time complexity of O(nĀ²) due to the nested loops. However, this is not efficient for large inputs.
Verified Code Solutions
function validNestedTags(tags) {
let stack = [];
for (let tag of tags) {
if (tag.startsWith('</')) {
if (stack.length === 0 || stack.pop() !== tag.slice(2, -1)) {
return false;
}
} else {
stack.push(tag);
}
}
return stack.length === 0;
}function validNestedTags(tags) {
let stack = [];
for (let tag of tags) {
if (tag.startsWith('</')) {
if (stack.length === 0 || stack.pop() !== tag.slice(2, -1)) {
return false;
}
} else {
stack.push(tag);
}
}
return stack.length === 0;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.