LeetCode 20. Valid Parentheses

Problem Description

Difficulty: Easy

Given a string s consisting only of the characters (, ), {, }, [, and ], determine whether the input string is valid.

A string is considered valid if:

1. Open brackets are closed by the corresponding type of brackets.
2. Open brackets are closed in the proper sequence.
3. Each closing bracket has a matching opening bracket of the same type.

Examples:

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

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

Input: "(("
Output: false

Constraints:

1 <= s.length <= 10^4
s consists only of the characters '()[]{}'

Initial Solution

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1:  # Odd length strings can't be valid
            return False
            
        valid_pairs = {")": "(", "]": "[", "}": "{"}
        stack = []
        
        for char in s:
            if char in "([{":  # If an opener then push to stack
                stack.append(char)
            elif not stack or stack.pop() != valid_pairs[char]:
                return False
        return not stack  # True if len(stack) == 0

# Tests
solution = Solution()
print(solution.isValid("({[]})"))  # True
print(solution.isValid("([)]"))  # False
print(solution.isValid("(("))  # False
print(solution.isValid(")"))  # False

True
False
False
False

This problem is fairly easy if you’re familiar with a stack, but more difficult otherwise. I added a check for odd numbered strings to return early, which gave a little performance boost. The solution above beats around 87% of LeetCode submission on runtime.

Just fun, I thought I’d try out Python’s match case statement. It’s new in Python 3.10 and could potentially give us another slight performance increase.

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) & 1: 
            return False

        stack = []
        valid_pairs = {')': '(', ']': '[', '}': '{'}

        for char in s:
            match char:
                case '(' | '[' | '{':
                    stack.append(char)
                case closing if closing in valid_pairs:
                    if not stack or stack.pop() != valid_pairs[closing]:
                        return False
        return not stack

# Tests
solution = Solution()
print(solution.isValid("({[]})"))  # True
print(solution.isValid("([)]"))  # False
print(solution.isValid("(("))  # False
print(solution.isValid(")"))  # False

True
False
False
False

This solution ran in 23 ms on LeetCode and beat 98.7% of submissions on runtime. I’m not sure I trust LeetCode’s timings completely though. I played around with timeit, which suggested it runs slower, at least with a very limited test set (the above tests plus a test of 7000 repeating parentheses/brackets).

To save a tiny fraction of memory, you could delete the valid_pairs dictionary and directly match each parenthesis/bracket. For example, with variations of the code below for each different type. It’s a little more readable but would be repetitive. It also ran a little slower on LeetCode too for whatever reason, perhaps a dictionary lookup is quicker.

match char:
    case ')':
        if not stack or stack.pop() != '(':
            return False

LeetCode’s results can be quite variable; however, the match case approach was generally faster there. I also tried using stack = deque() instead of a list, which improved some of my attempts but not the final one above.

The worst-case complexity for both solutions above is as follows:

• Time complexity: \(O(n)\) for the single loop
• Space complexity: \(O(n)\) for the stack

NeetCode Solution

NeetCode’s approach was basically the same, except for the lack of early exit for odd numbered strings. He also used stack[-1] rather than stack.pop(). It’s the same idea though.