Optimal Python Solution for Valid Parentheses (Interview Script)

2025-09-30

The Logic

• Parentheses must close in the reverse order they are opened.
• A stack naturally models last-in, first-out behavior.
• Any mismatch or leftover opening bracket invalidates the string.

Implementation / Diagram

Key Invariant

The stack always contains unmatched opening brackets in the order they must be closed.

def isValid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

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

    return not stack