LeetCode 20: Valid Parentheses

Problem Restatement

We are given a string s containing only these six bracket characters:

( ) { } [ ]

We need to determine whether the bracket string is valid.

A string is valid when:

1. Every opening bracket is closed by the same type of bracket.
2. Opening brackets are closed in the correct order.
3. Every closing bracket has a matching opening bracket of the same type.

For example:

"()[]{}"

is valid.

But:

"([)]"

is invalid, because [ is opened after (, so ] must close before ). The source statement defines exactly these bracket types and validity rules.

Input and Output

Example function shape:

def isValid(s: str) -> bool:
    ...

Examples

Example 1:

s = "()"

The opening bracket ( is closed by ).

Output:

true

Example 2:

s = "()[]{}"

Each pair is complete and correctly ordered.

Output:

true

Example 3:

s = "(]"

The opening bracket ( cannot be closed by ].

Output:

false

Example 4:

s = "([)]"

The brackets are closed in the wrong order.

Output:

false

Example 5:

s = "{[]}"

The inner [] closes first, then the outer {} closes.

Output:

true

First Thought: Count Brackets

One tempting idea is to count each bracket type.

For example, count how many ( and ) appear.

But counts alone are not enough.

Consider:

"([)]"

The counts are balanced:

But the string is still invalid because the closing order is wrong.

We need to track nesting order, not only counts.

Key Insight

Brackets follow a last-opened, first-closed rule.

For example:

{ [ ( ) ] }

The most recent opening bracket is (, so it must be closed by ) before [ or { can close.

This is exactly the behavior of a stack.

A stack lets us:

• push opening brackets
• pop the most recent opening bracket when we see a closing bracket
• check whether the popped bracket matches the closing bracket

Visual Walkthrough

Use:

s = "{[]}"

Start with an empty stack.

Read {:

stack = ["{"]

Read [:

stack = ["{", "["]

Read ].

The top of the stack is [.

It matches ], so pop it:

stack = ["{"]

Read }.

The top of the stack is {.

It matches }, so pop it:

stack = []

The string is finished and the stack is empty.

So the string is valid.

Now compare:

s = "([)]"

Read (:

stack = ["("]

Read [:

stack = ["(", "["]

Read ).

The top of the stack is [, but ) needs (.

Mismatch.

Return false.

Algorithm

1. Create an empty stack.
2. Create a map from closing bracket to matching opening bracket.
3. Scan each character in s.
4. If the character is an opening bracket, push it.
5. If the character is a closing bracket:
   • if the stack is empty, return false
   • pop the top opening bracket
   • if it does not match, return false
6. After scanning all characters, return whether the stack is empty.

Correctness

The stack stores opening brackets that have not been closed yet.

Its top is always the most recently opened unmatched bracket.

When the algorithm sees a closing bracket, the only bracket that may legally match it is the top of the stack. If the stack is empty, there is no opening bracket for this closing bracket. If the top has a different type, the closing order or bracket type is invalid.

If the top matches, popping it correctly marks that pair as closed.

After all characters are processed, any remaining opening bracket in the stack has no matching closing bracket. So the string is valid exactly when the stack is empty.

Therefore the algorithm returns true exactly for valid bracket strings.

Complexity

Implementation

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ")": "(",
            "}": "{",
            "]": "[",
        }

        stack = []

        for char in s:
            if char in pairs:
                if not stack:
                    return False

                top = stack.pop()

                if top != pairs[char]:
                    return False
            else:
                stack.append(char)

        return len(stack) == 0

Code Explanation

The map stores the required opening bracket for each closing bracket:

pairs = {
    ")": "(",
    "}": "{",
    "]": "[",
}

The stack stores unmatched opening brackets:

stack = []

When char is a closing bracket:

if char in pairs:

we need a previous opening bracket.

If the stack is empty:

if not stack:
    return False

then this closing bracket has nothing to close.

Otherwise, pop the most recent opening bracket:

top = stack.pop()

Check whether it matches:

if top != pairs[char]:
    return False

If char is not a closing bracket, it must be an opening bracket, so push it:

stack.append(char)

At the end:

return len(stack) == 0

The stack must be empty for all brackets to be closed.

Testing

def run_tests():
    s = Solution()

    assert s.isValid("()") is True
    assert s.isValid("()[]{}") is True
    assert s.isValid("(]") is False
    assert s.isValid("([)]") is False
    assert s.isValid("{[]}") is True
    assert s.isValid("]") is False
    assert s.isValid("((") is False
    assert s.isValid("([]{})") is True

    print("all tests passed")

run_tests()