Leetcode 20. Valid Parentheses

Let's understand what we're being asked to do. Given a string like '([{}])', we need to verify that every closing bracket properly matches its corresponding opening bracket.

Tracing through: we see '(' (opening), then '[' (opening), then '{' (opening), then '}' (must match the most recent unmatched opening, which is '{' ✓), then ']' (must match '[' ✓), then ')' (must match '(' ✓). All matched correctly!

But consider '([)]': we see '(' opening, '[' opening, then ')' tries to close - but the most recent unmatched opening is '[', not '('! This is invalid.

Important constraint: Every closing bracket must match the most recent unmatched opening bracket, and the types must match ('(' with ')', '[' with ']', '{' with '}').

Edge cases to consider: What if we have ')(' (closing before opening)? What if we have '((' (not all brackets closed)? What if the string is empty (should that be valid)?

The most recently opened bracket must match with the next closing bracket we encounter.

This creates a 'last-in, first-out' matching pattern where nested structures naturally resolve from innermost to outermost. For example, in '([{}])', the '{' opened last (among unmatched brackets) must close first.

This observation means we need a way to remember opening brackets in reverse order of how we'll match them.

The most recent opening bracket should be the easiest to access when we see a closing bracket. This 'last-in, first-out' property is exactly what makes certain data structures perfect for this problem.

Imagine a stack of plates. When you see '(', you add a plate labeled '('. When you see ')', you need to check if the top plate matches.

If it does, remove it (matched!). If not, or if no plates exist, it's invalid. This physical analogy maps perfectly to the bracket matching problem - you always deal with the most recently added item first.

Use a stack to track opening brackets as we scan the string left-to-right. When we encounter an opening bracket, push it onto the stack. When we encounter a closing bracket, check if the top of the stack contains the matching opening bracket. If it matches, pop the stack; if not (or if the stack is empty), the string is invalid. After processing all characters, the stack should be empty for a valid string.

def is_valid(s):
    """
    Check if a string of parentheses/brackets is valid.
    Uses a stack to track opening brackets and verify matching pairs.
    """
    # Map closing brackets to their corresponding opening brackets
    bracket_map = {')': '(', '}': '{', ']': '['}
    
    # Initialize stack to track opening brackets
    stack = []
    
    # Scan each character in the string
    for char in s:
        # If it's a closing bracket
        if char in bracket_map:
            # Check if stack is empty or top doesn't match
            if not stack or stack[-1] != bracket_map[char]:
                return False
            # Pop the matching opening bracket
            stack.pop()
        else:
            # It's an opening bracket, push to stack
            stack.append(char)
    
    # Valid if stack is empty (all brackets matched)
    return len(stack) == 0

• Stack for nested matching: Whenever you encounter problems with paired symbols that must match in reverse order (last opened, first closed), a stack is the natural choice because its LIFO property mirrors the nesting structure - opening brackets push, closing brackets pop and validate.
• HashMap for O(1) pair lookup: Use a dictionary/map to store bracket pairs (closing bracket as key, opening as value) rather than multiple if-statements - this makes validation a single lookup operation and keeps the code clean and extensible for new bracket types.
• Early termination optimization: Check for mismatched closing brackets immediately when popping from the stack, and verify the stack is empty at the end - both conditions must be true for validity, and failing either means you can return false without further processing.
• Empty stack edge case: The most common bug is popping from an empty stack when encountering a closing bracket with no matching opener - always check `if stack is empty` before popping to avoid runtime errors, or handle the exception gracefully.
• Balanced structure validation pattern: This stack-based matching technique extends beyond brackets to any hierarchical validation problem: HTML/XML tag matching, function call validation, expression parsing, and even checking balanced chemical equations - recognize the pattern of "things that open must close in reverse order".
• Space-time tradeoff awareness: The O(n) space for the stack is necessary and optimal - you cannot validate nested structures in less space because you must remember all unmatched opening brackets until their closers appear, making this the most efficient possible solution at O(n) time and O(n) space.