Valid Parentheses — LeetCode Solution in Python

The problem, in short

You are given a string made up only of the six bracket characters (), [] and {}. Decide whether the string is well formed: every opening bracket must be closed by the matching kind of bracket, and brackets must close in the reverse of the order they were opened.

An empty string counts as valid.

How to think about it

The instinct is to count brackets, and it is wrong. A counter says ([)] is fine — one of each, all balanced — when it plainly is not. Counting throws away order, and order is exactly what the problem is testing.

What the rule “closes in reverse order” describes is a stack. The most recently opened bracket is always the next one that must close. So: push every opening bracket; on every closing bracket, the thing on top of the stack must be its partner. If it is not, the string is invalid. If the stack is empty at the very end, every bracket found its pair.

The brute-force approach

A common first attempt is to repeatedly delete adjacent matching pairs until nothing changes, then check whether the string is empty.

def is_valid_brute(s):
    while True:
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            return s == ""
        s = shorter

It is correct, and it is a genuinely useful way to see the structure of the problem. But each pass rebuilds the whole string, and you may need many passes, so deeply nested input costs O(n²) time. The stack does the same job in one pass.

The optimised approach

Keep a dictionary that maps each closing bracket to the opening bracket it requires. Walk the string once. An opening bracket gets pushed. A closing bracket must find its partner on top of the stack — pop and compare. At the end, a leftover stack means something was opened and never closed.

Mapping closing to opening rather than the other way round is a small but real simplification: membership in the dictionary becomes the test for “is this a closing bracket?”, so you need only one lookup table instead of two.

Python solution

def is_valid(s):
    """Return True if every bracket in s is closed correctly and in order."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for char in s:
        if char in pairs:                       # a closing bracket
            # Pop the most recent opening bracket; the sentinel handles
            # a closing bracket arriving when the stack is empty.
            if not stack or stack.pop() != pairs[char]:
                return False
        else:                                   # an opening bracket
            stack.append(char)

    return not stack                            # nothing left open

Time and space complexity

Each character is pushed at most once and popped at most once, so the work is linear in the length of the string. The stack grows largest when the string is entirely opening brackets — "(((((" — which is where the O(n) space comes from.

Example walkthrough

Take s = "{[]}".

The stack is empty at the end, so the string is valid. Run "([)]" through the same table and it fails at index 2: the top of the stack is [, but ) requires (.

Common mistakes

1. Popping an empty stack. A string that starts with a closing bracket, like ")(", hits stack.pop() with nothing there and raises IndexError. The not stack check has to come first, and Python's short-circuiting is what makes that one line safe.
2. Forgetting the final stack check. "(((" never fails inside the loop — there are no closing brackets to disagree with. Returning True without testing not stack marks it valid.
3. Counting instead of stacking. Any solution based on tallies accepts "([)]". Order is the whole problem.
4. Only handling one bracket type. Matching ( against any closing bracket accepts "(]". The pop must compare the kind, not just the presence.

Related problems

• Min Stack — Designing a stack that also answers “what is the minimum?” in O(1).
• Longest Valid Parentheses — The hard sibling — stack of indices, not characters.
• Generate Parentheses — The same validity rule, used to build strings instead of check them.

More write-ups are indexed in Boopathi's LeetCode solutions.