Valid Parentheses

You'll use a stack to remember the brackets that are still open. You need lists, append, and pop. Related chapter: stacks.

1. The problem

You get a string made only of ()[]{}. Return whether every bracket closes with the same type, in the right order. This is LeetCode 20. Our function also treats an empty string as valid.

"([)]" is the trap. It has one of each bracket, so counting isn't enough: the order matters too.

2. A correct baseline

def baseline(text):
    while True:
        smaller=text.replace('()','').replace('[]','').replace('{}','')
        if smaller==text:
            return text==''
        text=smaller

assert baseline('([]){}')
assert not baseline('([)]')
assert not baseline(')')

This deletes matched pairs until nothing changes. On deeply nested input like ((((...)))), each pass removes only one pair. So it takes O(n²) time in the worst case: the work grows with the square of the string's length. On 10,000 characters, that's about 25 million characters copied. It uses O(n) space for the copies.

The bottleneck. Each pass rescans the open brackets it has already seen, instead of remembering which ones are still open.

3. The observation

Read ([]) left to right. When ] arrives, it must close the [, the most recent bracket still open. When ) arrives, the [ is closed, so ) must close the (.

So each closing bracket must match the most recent open bracket that's still open. Last opened, first closed: that's a stack. Push each open bracket. On each closing bracket, pop and check that the types match.

4. The solution and a trace

class Solution:
    def isValid(self, s: str) -> bool:
        """Input contains brackets only; empty input is valid."""
        pairs={')':'(',']':'[','}':'{'}
        stack=[]
        for char in s:
            if char in '([{':
                stack.append(char)
            elif not stack or stack.pop()!=pairs[char]:
                return False
        return not stack

solve=Solution().isValid
assert solve('([]){}')
assert not solve('([)]')
assert not solve(')')
assert solve('')

Trace ([]):

5. Why it works

What stays true. After each character, the stack holds exactly the brackets that are still open, oldest at the bottom.

A False answer is right. A closing bracket must close the newest open bracket. Closing anything deeper would cross pairs, as in ([)]. So a mismatch, or a closing bracket with nothing open, means the string is invalid.

A True answer is right. If every closing bracket matched and nothing is left open, every bracket has a partner in the right order.

6. Cost, edge cases, and failure

Cost. One pass: O(n) time, growing in step with the string. The stack takes O(n) space in the worst case, when every bracket is open.

Edge cases. Check that the stack isn't empty before popping. In not stack or stack.pop() != ..., Python's or skips the pop when the stack is empty. A string that ends with brackets still open, like "((", returns False through return not stack.

Where it fails. Matching counts don't prove the order is right:

assert '([)]'.count('(')=='([)]'.count(')')
assert not solve('([)]')  # Deliberate counterexample to counting-only validation.

import random
rng=random.Random(20)
for _ in range(600):
    text=''.join(rng.choices('()[]{}',k=rng.randrange(25)))
    assert solve(text)==baseline(text)