Valid Parentheses

Problem Description

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

Naive Approach

A naive approach would involve iterating through the string and checking for adjacent pairs that can be removed (e.g., "()", "{}", "[]"). This process would repeat until either the string is empty (valid) or no more pairs can be removed (invalid).

While this might work for some simple cases, it's inefficient and doesn't handle nested structures correctly.

Optimal Approach: Using a Stack

The optimal approach involves using a stack to keep track of opening brackets. Here's how it works:

1. Iterate through the string, character by character.
2. If the character is an opening bracket ((, {, or [), push it onto the stack.
3. If the character is a closing bracket (), }, or ]):
   • Check if the stack is empty. If it is, the string is invalid (because there's no corresponding opening bracket).
   • Pop the top element from the stack.
   • Check if the popped element is the matching opening bracket for the current closing bracket. If not, the string is invalid.
4. After iterating through the entire string, check if the stack is empty. If it is, the string is valid; otherwise, it's invalid (because there are unclosed opening brackets).

Edge Cases

• Empty string: Should be considered valid.
• String with only opening brackets: Invalid.
• String with only closing brackets: Invalid.
• Mismatched brackets: Invalid (e.g., "(}").
• Correctly nested brackets: Valid (e.g., "([]){}").

Code (Python)

def isValid(s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n) in the worst case, where n is the length of the string. This occurs when the string contains only opening brackets, and all of them are pushed onto the stack.