Leetcode 20. Valid Parentheses

Problem

Given a string containing only the characters (, ), {, }, [, and ], determine if the input string represents a valid bracket sequence.

A string is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type
• Opening brackets are closed in the correct order
• Each closing bracket matches the most recently opened unmatched opening bracket

Requirements

1. Return true if the string is valid, false otherwise
2. Handle all three types of brackets: parentheses (), square brackets [], and curly braces \{\}
3. Properly validate nested bracket structures
4. Account for empty strings (which should return true)

Constraints

• 0 <= s.length <= 10^4
• The string consists only of the characters: (, ), {, }, [, ]
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Examples

Example 1:

Input: s = "()" Output: true Explanation: A single pair of parentheses is valid.

Example 2:

Input: s = "()[]{}" Output: true Explanation: Multiple bracket pairs in sequence, all properly matched.

Example 3:

Input: s = "(]" Output: false Explanation: The opening parenthesis is incorrectly matched with a closing square bracket.

Example 4:

Input: s = "{[]}" Output: true Explanation: Square brackets are properly nested within curly braces.

Example 5:

Input: s = "([)]" Output: false Explanation: The brackets are interleaved incorrectly. The opening square bracket is inside the parentheses but its closing bracket is outside.

Hint 1: Data Structure Think about a data structure that naturally handles "last in, first out" operations. When you encounter a closing bracket, you need to check if it matches the most recent unmatched opening bracket.

Hint 2: Matching Strategy Create a mapping between closing brackets and their corresponding opening brackets. As you iterate through the string, push opening brackets onto your data structure and pop them when you encounter their matching closing bracket.

Hint 3: Edge Cases Consider what should happen when:

• You encounter a closing bracket but have no opening brackets to match
• You finish processing the string but still have unmatched opening brackets
• The string is empty

Full Solution ` def isValid(s: str) -> bool: # Stack to track opening brackets stack = []

# Map closing brackets to their corresponding opening brackets
bracket_map = {
    ')': '(',
    ']': '[',
    '}': '{'
}

# Process each character in the string
for char in s:
    if char in bracket_map:
        # It's a closing bracket
        # Check if stack is empty or top doesn't match
        if not stack or stack[-1] != bracket_map[char]:
            return False
        # Pop the matching opening bracket
        stack.pop()
    else:
        # It's an opening bracket, push to stack
        stack.append(char)

# Valid only if all brackets were matched (stack is empty)
return len(stack) == 0

`

Approach:

1. Use a stack data structure to track unmatched opening brackets

2. Create a dictionary mapping each closing bracket to its corresponding opening bracket

3. Iterate through each character in the string:

   • If it's a closing bracket, verify that the stack is not empty and the top element matches the expected opening bracket, then pop from the stack
   • If it's an opening bracket, push it onto the stack

4. After processing all characters, the string is valid only if the stack is empty (all brackets were matched)

Time Complexity: O(n) where n is the length of the string. We iterate through the string once, and each stack operation (push/pop) is O(1).

Space Complexity: O(n) in the worst case where all characters are opening brackets and we store them all in the stack.

Why This Works:

The stack naturally maintains the "most recent unmatched opening bracket" property we need. When we encounter a closing bracket, the top of the stack contains the most recent opening bracket that hasn't been matched yet. By checking if they correspond to the same bracket type, we ensure proper nesting and ordering.