Valid parentheses
We'll cover the following
Check that every bracket in the string is closed by the right kind, in the right order.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
push{0
[1
(2
)3
(4
)5
]6
}7
(8
[9
{10
}11
]12
)13
[14
]15
{16
(17
)18
}19
"{" opens a bracket. Push it and wait for its closer.
stack {
1 / 21
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | Each bracket is pushed and popped at most once. |
In Python
def is_valid(s):
pair = {')': '(', ']': '[', '}': '{'}
st = []
for ch in s:
if ch in pair:
if not st or st.pop() != pair[ch]: return False
else:
st.append(ch)
return not stSummary: say it in the interview
- Push each opener. A closer must match the most recent opener, which is the top of the stack. At the end the stack must be empty.
- Time O(n), space O(n). Each bracket is pushed and popped at most once.