Valid Parenthesis

Question

Recently, I've solved the "Valid Parenthesis" problem on LeetCode:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

I've decided to iterate over every character in the string and push it on stack if it is an opening bracket. If not, pop from the stack and check if the closing bracket matches the opening bracket.

Here is my implementation:

OPENING_BRACKETS = {"{", "[", "("}
BRACKETS_MAP = {"]": "[", "}": "{", ")": "("}


class Solution(object):
    def isValid(self, s):
        if not s:  # empty string is a valid string
            return True

        if s[0] not in OPENING_BRACKETS:
            return False  # early exit if string does not start with an opening bracket

        stack = []
        for index, bracket in enumerate(s):
            if bracket in OPENING_BRACKETS:
                stack.append(bracket)
            else:
                try:
                    last_opening_bracket = stack.pop()
                    if last_opening_bracket != BRACKETS_MAP[bracket]:  # last closing bracket does not match last opening bracket
                        return False
                except IndexError:
                    return False  # pop from an empty stack means the brackets are not balanced

        return not stack  # if something left on stack, brackets are unbalanced

Is it the most optimal approach to solving the problem Time- and Space- Complexity wise? What would you suggest to improve in the presented solution?

Answer 1

Flow control

The if not s: and if s[0] not in OPENING_BRACKETS: tests are pointless special cases. They obscure the fact that your general case already works. Furthermore, they don't improve performance by any noticeable amount. So, don't clutter your code with unnecessary statements.

You never use index, so you don't need enumerate().

Instead of handling stack underflow using try-except, you should just test whether stack is empty. The code would be clearer, and it would not be as deeply nested.

First rewrite:

OPENING_BRACKETS = {"{", "[", "("}
BRACKETS_MAP = {"]": "[", "}": "{", ")": "("}

def isValid(s):
    stack = []
    for bracket in s:
        if bracket in OPENING_BRACKETS:
            stack.append(bracket)
        elif not stack:
            return False        # Can't pop from an empty stack
        elif stack.pop() != BRACKETS_MAP[bracket]:
            return False        # Closing the wrong kind of bracket
    return not stack

The only difference is that this function crashes if s is None, whereas your solution returns True. I consider crashing to be reasonable behaviour.

Smarter use of BRACKETS_MAP

There is redundancy between OPENING_BRACKETS and BRACKETS_MAP. You can invert the BRACKETS_MAP to make … in BRACKETS_MAP do something useful. When you push a character onto the stack, push the expected matching delimiter instead.

BRACKETS_MAP = {"[": "]", "{": "}", "(": ")"}

def isValid(s):
    stack = []
    for bracket in s:
        if bracket in BRACKETS_MAP:
            stack.append(BRACKETS_MAP[bracket])
        elif not stack or bracket != stack.pop():
            return False
    return not stack