Problem Statement

Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', we need to determine if the input string is valid. An input string is considered valid if the following conditions are met:

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

Let's walk through the steps to solve this problem using Python.

Solution Approach

The given solution utilizes a stack data structure to efficiently check the validity of the input string. Here's a breakdown of the steps involved:

  1. Initialize an empty stack to keep track of opening brackets encountered in the input string.
  2. Create a mapping dictionary (map) to map closing brackets to their corresponding opening brackets. For example, ')' corresponds to '('.
  3. Iterate through each character in the input string.
  4. For each character:
  • If the stack is not empty, the current character is a closing bracket, and the top of the stack contains the corresponding opening bracket, pop the element from the stack as they form a valid pair.
  • Otherwise, if the character is not a closing bracket or if it doesn't match the corresponding opening bracket at the top of the stack, push it onto the stack.
  1. After processing all characters in the string, check if the stack is empty. If it is, return True, indicating that the input string is valid; otherwise, return False.

Now, let's dive into the code and provide detailed commentary for better understanding.

class Solution:
    def isValid(self, s: str) -> bool:
        # Initialize an empty stack to keep track of opening brackets
        stack = []
        # Create a mapping dictionary to map closing brackets to their corresponding opening brackets
        mapping = {")": "(", "]": "[", "}": "{"}

        # Iterate through each character in the input string
        for char in s:
            # If the stack is not empty and the current character is a closing bracket,
            # and the top of the stack contains the corresponding opening bracket,
            # pop the element from the stack as they form a valid pair
            if stack and char in mapping and stack[-1] == mapping[char]:
                stack.pop()
            # Otherwise, if the character is not a closing bracket or if it doesn't match
            # the corresponding opening bracket at the top of the stack, push it onto the stack
            else:
                stack.append(char)
        
        # After processing all characters in the string, check if the stack is empty
        # If it is, return True indicating that the input string is valid; otherwise, return False
        return len(stack) == 0

This solution efficiently solves the problem with a time complexity of O(n), where n is the length of the input string s. By using a stack, we can maintain the order of brackets and quickly check for validity.

I hope this article has provided you with a clear understanding of how to approach and solve the valid parentheses problem. Happy coding!