Valid Parentheses (LeetCode 20)

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

An input string is valid if:

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

Solution for valid parenthesis in Python

Approach: Using a Stack

Steps

1. Use a stack to keep track of opening brackets.
2. Iterate through the string:
• If the character is an opening bracket ((, {, [), push it to the stack.
• If the character is a closing bracket (), }, ]):
• Check if the stack is empty (if yes, return False).
• Pop the top element from the stack and check if it matches the correct opening bracket.
• If it doesn’t match, return False.

3. At the end, if the stack is empty, return True (all brackets matched properly), otherwise return False.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {')': '(', '}': '{', ']': '['}  # Closing to opening mapping
        
        for char in s:
            if char in mapping:  # If it's a closing bracket
                top_element = stack.pop() if stack else '#'  # Pop if stack isn't empty
                if mapping[char] != top_element:  # Check for matching pair
                    return False
            else:
                stack.append(char)  # Push opening brackets onto stack
        
        return not stack  # Stack should be empty for valid parentheses

Edge Cases Considered

✅ Strings with only opening or only closing brackets: “((((“, “))))”
✅ Mixed but improperly nested brackets: “(]”, “({[)]}”
✅ Properly nested but with multiple types: “({[]})”
✅ Empty string: “” (should return True)

Which Method to Use?
✅ Stack-based approach is the best as it efficiently checks for valid bracket pairs in O(n) time.