Don't miss an edge case in the room
A stack makes sense once you've seen it. Make sure you don't blank on an edge case in the room: write it yourself in the 14-day free trial, and the learning engine brings it back before you forget it.
The problem
Given a string containing only the characters (, ), {, }, [ and ], return true if
the string is valid and false if it is not.
The string is valid when:
- Every opening bracket is closed by a bracket of the same type.
- Opening brackets are closed in the correct order: the most recent bracket still open is the
first one to be closed, so
([)]is not valid. - Every closing bracket has an opening bracket of the same type before it.
Constraints
- 1 <= length of the string <= 10^4
- The string contains only the characters
()[]{}.
Example
- Input
s = "{[(])}"- Output
false
Every bracket has a partner of its own kind, but the square pair and the round pair overlap: ] arrives while ( is still open.
How to solve it
Counting doesn't work. {[(])} has one bracket of each kind opened and closed, and it's still invalid. Counts know how many brackets are open, not which one opened last, and the last one opened has to close first. That is last in, first out: a stack.
So read the string once. For each opening bracket, push the closing bracket it needs. For each closing bracket, pop the top of the stack: if the stack was empty, or the popped bracket isn't this one, return false. At the end, the string is valid only if the stack is empty.
Valid Parentheses({[(])})
The run starts on "{[(])}".
Those checks are the three ways a string fails: a closer with nothing open, a closer that doesn't match the top, and openers left over at the end. The first two fail inside the loop; the last is the empty check after it. Name all three before you code.
The follow-up: what if there's only one kind of bracket? Then any closer can close any opener, so a counter is enough. Add one for (, subtract one for ), return false if it ever drops below zero, and check that it ends at zero. That's O(1) space.
Python solution
class Solution:
def check_valid(self, s: str) -> bool:
open_close_pairs = {
'(': ')',
'[': ']',
'{': '}'
}
stack = []
for c in s:
if c in open_close_pairs:
stack.append(open_close_pairs[c])
elif len(stack) == 0 or stack.pop() != c:
return False
return len(stack) == 0Time and space complexity
- Time O(n)
- Each character is read once, and every push and pop is constant time.
- Space O(n)
- A string of only opening brackets fills the stack.