Valid Parentheses, The Stack's Greatest Hit

The Problem

Given a string of (), [], and {}, decide whether every bracket is closed by the correct type, in the correct order.

Why a Stack?

Brackets nest. The most recently opened bracket must be the first one closed, that's last-in, first-out, exactly what a stack gives you.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:                 # a closing bracket
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:                            # an opening bracket
            stack.append(ch)
    return not stack                     # leftover opens => invalid

• Time: O(n)
• Space: O(n)

The Two Failure Modes

1. A closing bracket with nothing (or the wrong thing) on top of the stack.
2. Leftover unclosed brackets when the string ends.

Both are handled above, the final return not stack catches case 2.

Kernel Queen tip: Any time you see "matching", "nesting", or "most recent first", a stack is probably the answer.