Valid Parentheses

Return True if every bracket in s is closed by the right type, in the right order, with nothing left open.

([{}]) is valid: } closes {, then ] closes [, then ) closes (. ([)] has one of each pair but isn't valid: ) comes while [ is still open.

Counting can't tell these apart. You have to know which opener is the latest one still open.

Brackets nest, so the opener that came last has to close first. That's a stack: push each opener, and a closer has to match the top.

A match pops the top, and the opener under it is next in line. A closer that doesn't match the top, or comes when the stack is empty, settles it: the string is invalid.

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for c in s:
        if c not in pairs:
            stack.append(c)
        elif not stack or stack[-1] != pairs[c]:
            return False
        else:
            stack.pop()
    return not stack

pairs maps each closer to the opener it closes. Check that the stack isn't empty before reading its top, and return False at the first bad closer. The last line catches openers that never closed.

Run it on ([{}]).

The three openers go on the stack, so { ends up on top. Then each closer finds its match there: } pops {, ] pops [, and ) pops (. The stack ends empty, so the answer is True.

Try Break it. On ([)], the stage stops at ) with [ on top and returns False.

• Check for an empty stack before reading its top. )( fails at its first character.
• Check the type, not that something is open. When ) comes in ([)], the stack isn't empty, but its top is [.
• Don't return True because the scan finished. ((() ends with two openers still on the stack.
• An empty string is valid: nothing is left open.

Each character is read once, and each opener is pushed once and popped at most once, so time is O(n).

The stack can hold every character, as in ((((, so space is O(n). There are only six kinds of bracket, but the stack can still grow with n, so the space isn't O(1).