20. Valid Parentheses

Reformulated question¶

Given a string made only of ()[]{}, return True if brackets are properly matched and nested, else False.

Example:

s = "([)]" -> False
because ")" tries to close "(" after "[" was opened last

Key trick¶

Use a stack.

Push opening brackets.
On a closing bracket, it must match the last opening bracket pushed.
Valid means no mismatch during the scan and the stack is empty at the end.

Trap¶

Checking only counts instead of order.
Forgetting the empty-stack case before reading the top.
Forgetting that odd-length strings can never be valid.
Treating "([)]" as valid because counts match.

Why is this question interesting?¶

It is the simplest real use of a stack.

It tests matching, nesting, and invariant thinking.
It also shows how to reject invalid input as soon as possible.

Solve the problem with idiomatic python¶

class Solution:
    def isValid(self, s: str) -> bool:
        # Odd length cannot be fully paired.
        if len(s) % 2:
            return False

        match = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = []

        for ch in s:
            # Opening bracket: keep it for future matching.
            if ch not in match:
                stack.append(ch)
                continue

            # Closing bracket: must match the latest opening bracket.
            if not stack or stack[-1] != match[ch]:
                return False

            stack.pop()

        # All openings must be closed.
        return not stack

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("()", True),
        ("()[]{}", True),
        ("([])", True),
        ("{[]}", True),
        ("(]", False),
        ("([)]", False),
        ("]", False),
        ("(", False),
        ("((((", False),
        ("))))", False),
        ("", True),
        ("[]{}()", True),
    ],
)
def test_is_valid(s, expected):
    assert Solution().isValid(s) == expected

Comment my solution¶

Your solution is correct and interview-good, with small cleanup opportunities.

Good:
- Early odd-length rejection.
- Correct stack logic.
- Correct empty-stack guard before stack[-1].
Improve:
- Starting with stack = [s[0]] is less clean than looping from the start with an empty stack.
- close_brackets = brackets.keys() is unnecessary; if b in brackets: is enough.
- LeetCode guarantees length >= 1, but the cleaner version also works for "" in tests.

import pytest

class Solution:
    def isValid(self, s: str) -> bool:
        n = len(s)
        if n % 2 != 0:
            return False
        brackets = {")": "(", "]": "[", "}": "{"}
        close_brackets = brackets.keys()
        stack = [s[0]]
        for b in s[1:]:
            if b in close_brackets:
                if len(stack) == 0:
                    return False
                if stack[-1] != brackets[b]:
                    return False
                stack.pop()
            else:
                stack.append(b)

        return len(stack) == 0


@pytest.mark.parametrize(
    ("s", "is_valid"),
    [
        ("()", True),
        ("()[]{}", True),
        ("([])", True),
        ("(]", False),
        ("([)]", False),
        ("((((", False)
    ]
)
def test_isValid(s, is_valid):
    assert Solution().isValid(s) == is_valid

A simpler version is:

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2:
            return False

        match = {")": "(", "]": "[", "}": "{"}
        stack = []

        for ch in s:
            if ch in match:
                if not stack or stack[-1] != match[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)

        return not stack