Skip to content

20. Valid Parentheses

Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Solution

class Solution:
    def isValid(self, s: str) -> bool:
        t = []

        for c in s:
            if c in ['(', '{', '[']:
                t.append(c)

            if c in [')', '}', ']']:
                if len(t) == 0 or (not is_match(t.pop(), c)):
                    return False

        return len(t) == 0

def is_match(l: str, r: str) -> bool:
    match l:
        case '(':
            return r == ')'
        case '{':
            return r == '}'
        case '[':
            return r == ']'
        case _:
            return False