Solutions

# Use a stack to keep track of open an closed parentheses order.
# stack

# Stack: O(n) time, O(n) space
def is_valid(s: str) -> bool:
    if not s:
        return True
    
    stack = []
    for c in s:
        if c == '(':
            stack.append(')')
        elif c == '[':
            stack.append(']')
        elif c == '{':
            stack.append('}')
        else:
            if stack and stack[-1] == c:
                stack.pop()
            elif stack and stack[-1] != c:
                return False
            else:
                return False
    
    return len(stack) == 0


# Brute force: O(n^2) time, O(n) space
def is_valid(s: str) -> bool:
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '')
        s = s.replace('[]', '')
        s = s.replace('{}', '')
    return len(s) == 0