Easy

Valid Parentheses

029

Given a string containing only parentheses, brackets, and braces, return true when every opening character is closed by the same type in the correct order.

EXAMPLES

Example 1

Input
{
  "s": "()[]{}"
}

Output
true

FUNCTION SHAPE

s: string→bool

SOLUTION NOTE

Classic stack problem. Push opening brackets, pop and match closing brackets.

Reveal reference solution +

pythonREFERENCE

def isValid(self, s: str) -> bool:
    paren = {')': '(', '}': '{', ']': '['}
    stack = []
    for c in s:
        if c in paren:
            if not stack or stack[-1] != paren[c]:
                return False
            stack.pop()
        else:
            stack.append(c)
    return not stack

TimeO(n)

SpaceO(n)

Open on LeetCode ↗