valid_parentheses.py

class Solution:
    """LeetCode #20 - Valid Parentheses (Easy)
    https://leetcode.com/problems/valid-parentheses/

    `s` contains only the characters ()[]{}. It is valid when every bracket is
    closed by the matching type, in the correct order, and nothing is left open.
    """

    def isValid(self, s: str) -> bool:
        """Classic stack: the last bracket opened must be the first one closed.

        Key insight: brackets nest, i.e. they follow last-in-first-out order -
        which is exactly what a stack models. Push every opening bracket; on a
        closing bracket, the only thing that may sit on top of the stack is its
        partner.

        Two failure modes to handle explicitly:
          - a closing bracket with an empty stack -> nothing was opened;
          - a non-empty stack at the very end     -> something was never closed.

        Time:  O(n) - each character is pushed and popped at most once.
        Space: O(n) - "((((((" puts every character on the stack.
        """
        pairs = {")": "(", "]": "[", "}": "{"}   # closing -> expected opening
        stack = []

        for ch in s:
            if ch in pairs:                       # closing bracket
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:                                 # opening bracket
                stack.append(ch)

        return not stack                          # empty stack == everything closed