Valid Parantheses

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[', ']', 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 '()[]{}'

Examples:

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Solutions

Approach 1 : using stack

We use a stack to keep track of the open parentheses encountered.
We define a mapping dictionary that maps closing parentheses to their corresponding opening parentheses.
We iterate through the characters in the input string.
If we encounter an opening parenthesis, we push it onto the stack.
If we encounter a closing parenthesis, we check if it matches the top element of the stack. If not, the string is invalid. Otherwise, we pop the top element from the stack.
After processing all characters, if the stack is empty, the string is valid; otherwise, it's not.
This algorithm efficiently checks the validity of the string in a single pass and has a time complexity of O(n), where n is the length of the input string.

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []  # Initialize an empty stack
        # Define the mapping of closing parentheses to opening parentheses
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping:  # If the character is a closing parenthesis
                # Pop the top element from the stack if it's not empty, else use '#'
                top_element = stack.pop() if stack else "#"
                if (
                    mapping[char] != top_element
                ):  # If the mapping doesn't match the top element of the stack
                    return False  # The string is invalid
            else:
                stack.append(
                    char
                )  # If the character is an opening parenthesis, push it onto the stack

        return (
            not stack
        )  # If the stack is empty, the string is valid; otherwise, it's not

References

Leetcode - Valid Parantheses