Valid Parentheses easy

Problem Statement

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.

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

Input: s = "{[]}" Output: true

Steps and Explanation

The problem can be efficiently solved using a stack data structure. The algorithm works as follows:

1. Initialization: Create an empty stack.
2. Iteration: Iterate through the input string s character by character.
3. Opening Bracket: If the character is an opening bracket ('(', '[', or '{'), push it onto the stack.
4. Closing Bracket: 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 matching opening bracket. If the stack is not empty, pop the top element from the stack. If the popped element doesn't match the current closing bracket (e.g., popping '[' and encountering ')'), the string is invalid.
5. End of String: After iterating through the entire string, if the stack is empty, it means all opening brackets have been correctly closed, and the string is valid. Otherwise, there are unmatched opening brackets, and the string is invalid.

Code

def isValid(s: str) -> bool:
    """
    Determines if a string containing parentheses is valid.

    Args:
        s: The input string containing parentheses.

    Returns:
        True if the string is valid, False otherwise.
    """
    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 empty stack
        else:
            return False #Invalid Character

    return not stack  # True if stack is empty (all brackets matched)

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
• Space Complexity: O(n) in the worst case. The stack can grow to a size equal to the length of the input string if the string contains only opening brackets. In the best case (e.g., an empty string or a string with perfectly matched pairs), the space complexity is O(1).