Given a string s containing just the characters (, ), {, }, [, ], determine if the input string is valid. A 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.

Constraints

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

Examples

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

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

Input: s = "(]"
Output: false

Solution

The problem can be efficiently solved using a stack data structure.

Approach

  • Initialize an empty stack.
  • Create a mapping of closing brackets to their corresponding opening brackets (e.g., ')': '(', '}' : '{', ']' : '[').
  • Iterate through each character char in the input string s:
    • If char is an opening bracket ((, {, [), push it onto the stack.
    • If char is a closing bracket (), }, ]):
      • Check if the stack is empty. If it is, there's no matching opening bracket, so the string is invalid. Return false.
      • Pop the top element from the stack. Let's call it top_element.
      • Compare top_element with the expected opening bracket for char (using our mapping). If they don't match, the brackets are not correctly paired. Return false.
  • After iterating through the entire string, if the stack is empty, all opening brackets have been correctly closed. The string is valid. Return true.
  • If the stack is not empty, it means there are unclosed opening brackets. The string is invalid. Return false.

Python Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # Map closing brackets to their corresponding opening brackets
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping.values():  # It's an opening bracket
                stack.append(char)
            elif char in mapping:  # It's a closing bracket
                # If the stack is empty, no matching open bracket
                if not stack:
                    return False
                # Pop the top element and check if it matches
                top_element = stack.pop()
                if mapping[char] != top_element:
                    return False
            # If it's not a bracket (problem states only brackets, but good practice)
            # else:
            #     return False 
        
        # After iterating, if the stack is empty, all brackets are matched
        return not stack