LeetCode Solutions Blog

Valid Parentheses

Number: 20

Difficulty: Easy

Paid? No

Problem Description

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets in the correct order, and every closing bracket has a corresponding opening bracket.

Key Insights

The problem can be solved using a stack data structure.
When encountering an opening bracket, push it onto the stack.
When encountering a closing bracket, check if the top of the stack is its matching opening bracket.
If the stack is empty before finding a match or if there is a mismatch, the string is invalid.
At the end, the string is valid only if the stack is empty, meaning all brackets were properly matched.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we process each character once. Space Complexity: O(n) in the worst case for the stack when all characters are opening brackets.

Solution

We use a stack to check for valid parentheses. The algorithm iterates through the string, pushing opening brackets onto the stack and popping them when a corresponding closing bracket is encountered. A mapping of closing to opening brackets helps in validating the matching pairs. By ensuring that the stack is empty at the end, we confirm that every opening bracket was properly closed.

Code Solutions

def isValid(s: str) -> bool:
    # Mapping from closing brackets to their corresponding opening brackets.
    paren_map = {')': '(', '}': '{', ']': '['}
    # Initialize an empty list to use as a stack.
    stack = []
    # Process each character in the string.
    for char in s:
        # If the character is a closing bracket.
        if char in paren_map:
            # Pop the top element from the stack if available, else use a placeholder.
            top_element = stack.pop() if stack else '#'
            # Check if the mapping does not match the top element.
            if paren_map[char] != top_element:
                return False
        else:
            # For opening brackets, push onto the stack.
            stack.append(char)
    # Return True if all brackets are matched (i.e., the stack is empty).
    return not stack

# Example usage
print(isValid("()[]{}"))  # Expected output: True