Valid Parentheses

March 24, 2020

I’m trying to get in a habit of starting my mornings off with coffee and a Leetcode problem before work. Ease my way into the day and get the brain juices flowing. Let’s jump in!

Valid Parentheses


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

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid.

Example inputs:

Input: "()"
Output: true

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

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true


Past experience screams stack as the data structure to use here. This immediately reminded me of writing prefix and postfix calculators in college courses.

I tried a few solutions before that, hoping that the input test cases would be simple enough that I could bypass it. This ultimately failed, as I should have expected.

In short, my thinking was this:

If the input length isn’t an even number, you already know it’s inbalanced.

Iterate through each character of the input, push “open” symbols '(', '{', and '[' onto the stack and continue. When the character is a “close” symbol of ')', '}', or ']', pop from the stack and compare. The stack value should be a the opposite symbol that you’re currently on in a correctly balanced input.

Corner Cases

The following corner cases are what I missed in my initial solution:


The following are things I would improve from my original solution once it passed all the tests:


class Solution:
    open_symbols = ['(', '{', '[']
    close_symbols = [')', '}', ']']

    symbols = dict(zip(open_symbols, close_symbols))

    def __init__(self):
        self.stack = []

    def is_open(self, s: str) -> bool:
        return s in self.open_symbols

    def is_close(self, s: str) -> bool:
        return s in self.close_symbols

    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False

        for val in s:
            if self.is_open(val):
            if self.is_close(val):
                if len(self.stack) == 0:
                    return False
                prev = self.stack.pop()
                if val != self.symbols[prev]:
                    return False

        return len(self.stack) == 0


Runtime: 24 ms, faster than 90.39% of Python3 online submissions for Valid Parentheses.
Memory Usage: 13 MB, less than 98.26% of Python3 online submissions for Valid Parentheses.

Return home