Interview challenge · easy · stack, string

Valid Parentheses

The challenge

Given a string s containing only the characters ( ) [ ] { }, decide whether it is valid: every opening bracket must be closed by the same type of bracket, and brackets must close in the correct order.

Example

"()"      ->  true
"([]{})"  ->  true
"(]"      ->  false
"([)]"    ->  false

Idea: a stack. Push every opening bracket; on a closing one, the top of the stack must be its partner. At the end the stack must be empty. Time O(n), space O(n).

The solution

1# Valid Parentheses - ayotl.dev
2def is_valid(s):
3    # each closer -> the opener it needs
4    pairs = {")": "(", "]": "[", "}": "{"}
5    stack = []
6    for ch in s:
7        if ch in pairs:
8            # the last opener must match
9            if not stack:
10                return False
11            if stack.pop() != pairs[ch]:
12                return False
13        else:
14            stack.append(ch)  # remember it
15    # valid only if nothing is left open
16    return not stack
17
18
19for s in ["()", "([]{})", "(]", "([)]"]:
20    print(s, is_valid(s))

$ python3 valid_parentheses.py

() True

([]{}) True

(] False

([)] False

The video

Watch on YouTube →