Valid Parentheses

Easy#20brackets

You get a string of the brackets ( ) [ ] { }. It is valid when every bracket is closed by one of its own kind and the pairs never cross: what opened last closes first. Our example, two calls: "{[()()]}" gives true and "(()[]" gives false, the first "(" is never closed.

20 Valid ParenthesesWalkthrough · 1×

Example: "{[()()]}" and "(()[]". Below the strings is the stack of closers still expected, newest on the right.

call 1{[()()]}call 2(()[]expect—
not read yetch, read now; a closer just pushedopen, its closer is expectedpopped to compare; never closedclosed in a pair

First call, s = "{[()()]}": nothing is expected yet

01/43
restart · back · play · step
Speed
1function isValid(s):
2 expect = empty stack
3 for each ch in s:
4 if ch is ( or [ or {:
5 push closerOf(ch) onto expect
6 else if expect is empty:
7 return false
8 else if pop from expect is not ch:
9 return false
10 return expect is empty
state
s
"{[()()]}"
expect
[]
ch
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Pairs cannot cross, so the bracket a closer must match is always the newest one still open: the top of the stack. Pushing the closer it waits for turns the check into one comparison.
  2. A matched pair is popped at once, so whatever was nested inside is gone before the outer closer arrives, and the outer opener is on top again.
  3. Two ways to fail need their own checks: a closer with nothing expected, and an opener still waiting when the string ends. That is why the last line asks whether the stack is empty.

Complexity

Time O(n): each bracket is pushed or popped once. Memory O(n): a string of only openers puts all of them on the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.