Valid Parentheses#

Problem#

You are given a string containing only the characters (, ), {, }, [, and ]. Decide whether the string is valid. A string is valid when every opening bracket is closed by a matching bracket of the same type, and brackets close in the correct order (the most recently opened bracket must be the first one closed).

Example#

• Input: "([{}])" gives True.
• Input: "([)]" gives False, because the brackets interleave.
• Input: "(" gives False, because it is never closed.

Optimal approach#

This is a textbook stack problem. Scan the string left to right. When you see an opening bracket, push it onto a stack. When you see a closing bracket, the only way the string can still be valid is if the bracket at the top of the stack is its matching opener, so pop and compare. If the stack is empty when you hit a closer, or the popped opener does not match, the string is invalid. At the end the stack must be empty: any leftover opener was never closed.

A brute-force approach of repeatedly removing adjacent matched pairs like () also works, but it is O(n squared) because each pass rescans the string. The stack does it in a single pass.

Solution#

 1def is_valid(s: str) -> bool:
 2    pairs = {")": "(", "]": "[", "}": "{"}
 3    stack = []
 4    for char in s:
 5        if char in pairs:
 6            if not stack or stack.pop() != pairs[char]:
 7                return False
 8        else:
 9            stack.append(char)
10    return not stack
11
12
13print(is_valid("([{}])"))  # True
14print(is_valid("([)]"))    # False
15print(is_valid("("))       # False

Complexity#

• Time: O(n), one pass over the string.
• Space: O(n) in the worst case, when every character is an opener.

This is the canonical monotonic stack warm-up (here the stack tracks structure rather than values). Keep going with the 60-day challenge.