LeetCode 20: Valid Parentheses Solution in Python Explained

Problem Statement

LeetCode 20, Valid Parentheses, is an easy-level challenge where you’re given a string s containing only parentheses characters—'(', ')', '{', '}', '[', and ']'. Your task is to determine if the string is valid, meaning all opening brackets are closed by the same type in the correct order. Return True if valid, False otherwise. The string can be empty or contain any combination of these six characters.

Constraints

1 <= s.length <= 10^4: String length ranges from 1 to 10,000 characters.
s consists only of '(', ')', '{', '}', '[', ']'.

Example

Input: s = "()"
Output: true
Explanation: Open '(' is closed by ')'.

Input: s = "()[]{}"
Output: true
Explanation: Each pair—(), [], {}—is properly nested.

Input: s = "(]"
Output: false
Explanation: '(' is not closed by ']'.

Input: s = "([)]"
Output: false
Explanation: Nested incorrectly; '(' should close before ']'.

Understanding the Problem

How do you solve LeetCode 20: Valid Parentheses in Python? Imagine checking if a string like "()[]{}" has all its brackets matched correctly—each '(' needs a ')', '[' needs a ']', and '{' needs a '}'. A string like "(]" fails because the types don’t match, and "([)]" fails because the order is wrong. We need a method to track opening brackets and ensure they close properly. We’ll explore a Stack-Based Approach (optimal) and a Brute Force Approach (simpler but flawed) to understand this problem fully.

Solution 1: Stack-Based Approach (Primary)

Explanation

Use a stack to track opening brackets. Push each opening bracket onto the stack, and when a closing bracket appears, check if it matches the top of the stack. Pop the top if it does; otherwise, the string is invalid. At the end, the stack should be empty for a valid string.

Here’s a visual for "()[]":

Stack: []
'(' → Push '(' → Stack: ['(']
')' → Pop '(' (matches ')') → Stack: []
'[' → Push '[' → Stack: ['[']
']' → Pop '[' (matches ']') → Stack: []
End: Stack empty → Valid

Handle Edge Case.

If string is empty, it’s valid (no mismatches).

Define Bracket Mapping.

Map closing brackets to opening ones (e.g., ')': '(').

Use Stack.

Push opening brackets, check and pop for closing brackets.

Check Validity.

Stack empty means valid; non-empty means unpaired brackets.

Step-by-Step Example

Example 1: s = "()[]{}"

We have "()[]{}" and want to check validity.

Goal: Verify all brackets match correctly.
Result for Reference: True—each pair matches and nests properly.
Start: Stack is empty. Map: ')': '(', ']': '[', '}': '{'.
Step 1: Process '(' (position 0).

'(' is an opening bracket, push it onto the stack.
Stack: ['('].

Step 2: Process ')' (position 1).

')' is closing, top of stack is '('.
')' maps to '(', matches, pop '('.
Stack: [].

Step 3: Process '[' (position 2).

'[' is opening, push.
Stack: ['['].

Step 4: Process ']' (position 3).

']' maps to '[', matches top, pop.
Stack: [].

Step 5: Process '{' (position 4).

'{' is opening, push.
Stack: ['{'].

Step 6: Process '}' (position 5).

'}' maps to '{', matches, pop.
Stack: [].

Step 7: End of string.

Stack empty, all brackets paired.

Finish: Return True.

Example 2: s = "(]"

Now, "(]" to check.

Goal: Verify bracket matching.
Result for Reference: False—types don’t match.
Start: Stack empty, same map.
Step 1: '('.

Push '('.
Stack: ['('].

Step 2: ']'.

']' maps to '[', top is '(', no match, stop.

Finish: Return False.

How the Code Works (Stack-Based)

Here’s the Python code with a line-by-line explanation:

def isValid(s: str) -> bool:
    # Line 1: Check if string is empty
    if not s:
        # Line 2: Empty string has no mismatches, return True
        return True

    # Line 3: Define mapping of closing to opening brackets
    brackets = {')': '(', ']': '[', '}': '{'}
    # Line 4: Initialize empty stack to track opening brackets
    stack = []

    # Line 5: Iterate through each character in the string
    for char in s:
        # Line 6: Check if char is an opening bracket (in map values)
        if char in brackets.values():
            # Line 7: Push opening bracket onto stack
            stack.append(char)
        # Line 8: Check if char is a closing bracket (in map keys)
        elif char in brackets:
            # Line 9: If stack empty or top doesn’t match, invalid
            if not stack or stack.pop() != brackets[char]:
                # Line 10: Return False for mismatch or no opening
                return False

    # Line 11: After loop, check if stack is empty
    return len(stack) == 0
    # Line 12: True if empty (all paired), False if not

Alternative: Brute Force with Counting

Explanation

Count occurrences of each bracket type and check if pairs balance. This ignores nesting order, making it flawed but useful for comparison.

Count Brackets.

Tally each type of bracket.

Check Pairs.

Ensure counts match for '()', '[]', '{}'.

Return Result.

True if counts balance, False otherwise.

Step-by-Step Example (Brute Force)

For s = "()[]{}":

Goal: Check validity.
Result for Reference: True (works here but fails for nesting).
Start: Counters at 0.
Step 1: Count.

'('=1, ')'=1, '['=1, ']'=1, '{'=1, '}'=1.

Step 2: Check pairs.

'('=')', '['=']', '{'='}', all equal.

Finish: Return True.

For s = "([)]":

Goal: Check validity.
Result for Reference: False (should fail, but brute force says True).
Start: Counters at 0.
Step 1: Count.

'('=1, ')'=1, '['=1, ']'=1.

Step 2: Check pairs.

'('=')', '['=']', passes (incorrectly).

Finish: Returns True (wrong due to nesting).

Code (Brute Force)

Here’s the alternative Python code, simpler but flawed.

def isValidBrute(s: str) -> bool:
    # Line 1: Check if string is empty
    if not s:
        # Line 2: Empty is valid
        return True

    # Line 3: Initialize counters for each bracket type
    counts = {'(': 0, ')': 0, '[': 0, ']': 0, '{': 0, '}': 0}

    # Line 4: Count each character
    for char in s:
        # Line 5: Increment counter for this character
        counts[char] += 1

    # Line 6: Check if pairs match in count
    return (counts['('] == counts[')'] and 
            counts['['] == counts[']'] and 
            counts['{'] == counts['}'])
    # Line 7: True if all pairs equal, False otherwise

How the Code Works (Brute Force)

Line 1-2: If string is empty, return True—no brackets to mismatch.
Line 3: Set up a dictionary to count each bracket type, all starting at 0.
Line 4-5: Loop through the string, incrementing the count for each bracket encountered.
Line 6-7: Check if opening and closing counts match for all three types; return True if they do, False if any pair doesn’t balance.

Complexity

Stack-Based:

Time: O(n) – Single pass through the string.
Space: O(n) – Stack can grow to string length.

Brute Force:

Time: O(n) – One pass to count.
Space: O(1) – Fixed-size counter dictionary.

Efficiency Notes

The stack-based approach is the optimal solution for LeetCode 20, ensuring both matching and correct order in O(n) time with O(n) space. It’s reliable for all cases, including nesting. The brute force method is faster in execution but fails for order (e.g., "([)]"), making it unsuitable despite its simplicity.

Key Insights

Tips to master LeetCode 20:

Stack Tracks Order: Use a stack to enforce bracket sequence—counts alone miss nesting.
Match Immediately: Check closing brackets against the stack top right away for efficiency.
Empty is Easy: An empty string is valid by definition—handle it upfront.

Additional Example

For s = "{[]}":

Goal: Check validity.
Reference: True.
Stack Steps: Push '{', '[', pop for ']', pop for '}', stack empty.
Result: True.

Edge Cases

Empty: "" – Returns True.
Unpaired: "(" – Returns False.
Wrong Order: "([)]" – Returns False.
Single Type: "()" – Returns True.

Final Thoughts

The stack-based method is a clean, efficient way to solve LeetCode 20 in Python, ideal for interviews and bracket-matching problems. Check LeetCode 22: Generate Parentheses for more bracket challenges!