Day 2 - Valid Parentheses

Problem:

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 are closed by the same type of brackets.

2. Open brackets are closed in the correct order.

3. Every closing bracket has a corresponding open bracket of the same type.

Examples:

• Input: s = "()" → Output: true

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

• Input: s = "(]" → Output: false

• Input: s = "([])" → Output: true

How I Approach This:

The key insight is that every closing bracket must match the most recent unmatched opening bracket—making a stack the ideal data structure for this problem.

I’ll start by creating a dictionary to map each closing bracket to its corresponding opening bracket:

close_to_open = {')': '(', ']': '[', '}': '{'}

Next, I’ll initialize an empty list to use as a stack:

stack = []

Then, I’ll iterate through each character in the string:

• If it’s an opening bracket ((, {, [), I push it onto the stack.

• If it’s a closing bracket (), }, ]), I check whether the top of the stack matches its corresponding opening bracket:

  • If the stack is empty or the top doesn’t match, the string is invalid.

  • Otherwise, I pop the top element from the stack.

Finally, if the stack is empty at the end, all brackets matched correctly and the string is valid.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        close_to_open = {')': '(', ']': '[', '}': '{'}
        
        for char in s:
            if char in close_to_open:
                if stack and stack[-1] == close_to_open[char]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(char)
        
        return not stack