20. Valid Parentheses

EasyLeetCode

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

An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.
• 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

Example 4

Input: s = "([])"

Output: true

Example 5

Input: s = "([)]"

Output: false

Constraints

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

How to solve the problem

• Stack with Hash Table

Code

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

Complexity

• Approach 1: Stack with Hash Table

• Time complexity: O(n)

  • We traverse the string once, each character is processed in O(1) time

• Space complexity: O(n)

  • In worst case, we might need to store all opening brackets in the stack