Valid Parentheses challenge explained

The problem

We are going to take a look at the "Valid Parentheses" problem in this walkthrough. It asks us to determine if a given string of parentheses is valid. A valid string must have properly closed brackets, which means every opening bracket must have a corresponding closing bracket in the correct order. The string can contain three types of brackets: (), [], and {}.

The breakdown

We need to consider several aspects to work out a solution to this problem.

Matching pairs: Each type of bracket has a specific matching pair.

Order matters: Brackets must be closed in the reverse order of opening.

Balance: The number of opening and closing brackets must be equal.

Edge cases: Empty strings or strings with only one bracket.

Let's explore two approaches to solve this problem: a simple, intuitive approach and a more optimised solution.

Approach 1 - Simple

This approach involves iteratively removing valid pairs of brackets until no more can be removed.

This approach is intuitive and easy to understand. It repeatedly removes valid pairs of brackets until no more can be removed. The result is valid after the pairs have been removed and the final string is empty.

def is_valid_simple(s: str) -> bool:
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return len(s) == 0

# Test cases
print(is_valid_simple("()"))  # True
print(is_valid_simple("()[]{}"))  # True
print(is_valid_simple("(]"))  # False
print(is_valid_simple("([)]"))  # False
print(is_valid_simple("{[]}"))  # True

Pros

• Simple to implement and understand
• Handles nested structures correctly

Cons

• Inefficient for large inputs (O(n^2) time complexity in the worst case)
• Creates many intermediate strings, which is memory-intensive

Approach 2 - Optimal

The stack-based approach is the more efficient and commonly used approach for this problem.

This solution uses a stack, a data structure that follows the Last In First Out (LIFO) principle, to track opening brackets and efficiently check if closing brackets match the most recent opening bracket.

def is_valid(s: str) -> bool:
    stack = []
    bracket_map = {")": "(", "]": "[", "}": "{"}
    
    for char in s:
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map.keys():
            if not stack or stack.pop() != bracket_map[char]:
                return False
        else:
            # If the character is not a bracket, it's invalid
            return False
    
    return len(stack) == 0

# Test cases
print(is_valid("()"))  # True
print(is_valid("()[]{}"))  # True
print(is_valid("(]"))  # False
print(is_valid("([)]"))  # False
print(is_valid("{[]}"))  # True
print(is_valid(""))  # True
print(is_valid("("))  # False
print(is_valid(")"))  # False

How it works

• We iterate through each character in the string.
• If it's an opening bracket, we push it onto the stack.
• If it's a closing bracket, we check if the stack is empty (no matching opening bracket) or if the top of the stack doesn't match the current closing bracket. If either condition is true, the string is invalid.
• If the character matches, we pop the top element from the stack.
• After processing all characters, we check if the stack is empty. If it is, all brackets were closed correctly.

Time Complexity: O(n) where n is the length of the string. We traverse the string once.

Space Complexity: O(n) in the worst case, where the string contains only opening brackets.

Pros

• O(n) time complexity
• Handles all cases correctly, including nested structures
• It uses less memory than the simple approach

Cons

• It is slightly more complex to implement and understand compared to the simple approach

This stack-based solution is generally considered the best approach for the "Valid Parentheses" problem due to its efficiency and ability to handle all cases correctly.

When implementing this solution, it's important to consider edge cases:

• Empty string (valid)
• String with only one bracket (invalid)
• String with non-bracket characters (invalid in this context)

Using a hash map (bracket_map in the code) to store the bracket pairs makes the solution easily extensible to handle additional types of brackets if needed.