Solution Explanation: Valid Parentheses

This problem checks if a given string containing parentheses (), [], and {} is valid. A valid string means:

1. Matching Pairs: Every opening bracket has a corresponding closing bracket of the same type.
2. Correct Order: Closing brackets must come after their corresponding opening brackets.

Approach: Using a Stack

The most efficient approach uses a stack data structure. The algorithm iterates through the input string:

1. Opening Bracket: If an opening bracket ((, [, {) is encountered, it's pushed onto the stack. The stack keeps track of unmatched opening brackets.

2. Closing Bracket: If a closing bracket is encountered:

   • If the stack is empty (no matching opening bracket), the string is invalid, and false is returned.
   • The top element of the stack (the most recently encountered opening bracket) is popped.
   • If the popped opening bracket doesn't match the current closing bracket (e.g., ( and ]), the string is invalid, and false is returned.

3. End of String: After iterating through the entire string:

   • If the stack is empty, it means all opening brackets have been matched, and the string is valid; true is returned.
   • If the stack is not empty, it means there are unmatched opening brackets, and the string is invalid; false is returned.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input string. The algorithm iterates through the string once.
• Space Complexity: O(n) in the worst case. The stack could potentially store all the opening brackets if they are not matched until the end of the string. In the best-case scenario (a perfectly matched string), the space complexity is O(1).

Code Implementation (Python)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        bracket_map = {')': '(', '}': '{', ']': '['}
 
        for char in s:
            if char in bracket_map.values():  # Opening bracket
                stack.append(char)
            elif char in bracket_map.keys():  # Closing bracket
                if not stack or stack.pop() != bracket_map[char]:
                    return False  # Unmatched or stack empty
            else:
                return False #Invalid character
 
        return not stack  # True if stack is empty (all brackets matched)
 

This Python code efficiently implements the stack-based solution. The bracket_map dictionary provides a quick lookup for matching brackets. The if not stack or stack.pop() != bracket_map[char] line elegantly handles both the empty stack and mismatch conditions.

The implementations in other languages (Java, C++, Go, TypeScript, Rust, JavaScript, C#, Ruby, PHP) follow the same logic, adapting the syntax and data structures to each language's specifics, but the core algorithm remains the same.