Part 2 · Problems · Stack
Valid Parentheses
#20 · Easy · LeetCode
Is the bracket string balanced and correctly nested? Only ()[]{}.
()[]{} -> true
([)] -> false
{[]} -> true
Ask before coding
- Only these 6 characters?
- Empty string valid?
Hint
The most recent open bracket must close first.
Approach
Push open brackets. On a closing bracket, pop and check it matches. At the end the stack must be empty.
Time O(n) Space O(n)
Watch it run
Solution (JavaScript, tested)
function isValid(s) {
const pairs = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const c of s) {
if (c in pairs) {
if (stack.pop() !== pairs[c]) return false;
} else stack.push(c);
}
return stack.length === 0;
}Traps
- Forgetting the final empty check ('(' alone).
- A closing bracket on an empty stack: pop gives undefined, so it fails correctly.
Say out loud: Last opened, first closed: that's a stack.