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.

Constraints:

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

Example 1:

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

Example 2:

Input: s = "([)]"
Output: false

Solution

Approach: Utilize a stack data structure to keep track of open brackets.

  • Initialization: Create an empty stack and a bracket_map to store pairings of closing to opening brackets (e.g., ')' : '(').

  • Iteration: Iterate through each character in the input string s:

    • If the current character is a closing bracket (i.e., it's a key in bracket_map):
      • Check if the stack is empty or if the top element of the stack does not match its corresponding opening bracket from bracket_map.
      • If either condition is true, the string is invalid; return false.
      • Otherwise, if a match is found, pop the top element from the stack.
    • If the current character is an opening bracket:
      • Push it onto the stack.

  • Final Check: After iterating through the entire string, if the stack is empty, it means all open brackets have been correctly matched and closed. Return true.

  • If the stack is not empty, it implies there are unmatched open brackets. Return false.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        bracket_map = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in bracket_map: # It's a closing bracket
                # If stack is empty or top doesn't match the required open bracket
                if not stack or stack[-1] != bracket_map[char]:
                    return False
                stack.pop()
            else: # It's an opening bracket
                stack.append(char)

        # If the stack is empty, all brackets were matched
        return not stack