Valid Parentheses — Interview Question Guide

• Last-in, first-out matching makes a stack the natural data structure.
• A closing bracket must match the top of the stack; otherwise the string is invalid.
• At the end, the stack must be empty (no unclosed openers).

1. Map each closing bracket to its opening bracket.
2. Push opening brackets onto a stack.
3. For a closing bracket, if the stack is empty or the top does not match, return false; otherwise pop.
4. Return true only if the stack is empty at the end.

def is_valid(s):
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pair.values():
            stack.append(c)
        elif c in pair:
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
    return not stack