The Blind 75 Leetcode Series: Valid Parentheses

Photo by Chris Ried on Unsplash

Today, we will be working on Valid Parentheses.

Given a string s 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.

Some examples:

"()" # Valid
"()[]{}" # valid
"(]" # invalid
"([)]" # invalid

From the description, we want to check a few things

1. Are we going to see empty string? How do we treat it?
2. Is there a limit how long the length of string is?

We care about first question because we want to cover the case of zero length, and the definition can be ambiguous since it’s still a “valid” string because we did not violate any of the rule. At the same time, it does not contain any bracket, so we want to know about this edge case. We care about the second question because we most likely need to track the opening brackets, and we want to make sure we have enough memory to store these should we store all.

If the answers are “treat empty string as valid string” and “string length will be finite and we have sufficient memory to store”, then we can add to the problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string with zero length is considered valid, and length of s is finite and is << amount of space we have.

Let’s get to it.

We can work this problem in the way that we find all conditions that make this string invalid, check all of them, then see if we meet any of the conditions.

What are the conditions which make this string invalid?

1. An open bracket cannot find a counterpart of close bracket
2. A close bracket cannot find a counterpart of open bracket

We want to track:

1. number of each type of bracket
2. if an open bracket has a close bracket of the same type at the right position
3. if a close bracket has a open bracket of the same type at the right position

№1 can be included in №2 and №3, since the string will violate one of the conditions. So essentially we just need to keep track of all brackets and make sure the corresponding counterparts match up.

To put it even simpler, we just want to make sure a close bracket matches the last open bracket we see.

If we visited all the brackets and all close brackets match up, we just need to make sure there’s no more unmatched open bracket.

To realize this idea, we will introduce the concept of stack.

Wikipedia link for stack

Every time we see an open bracket, we add it to the top of stack. Every time we see a close bracket, we check if the top of stack is a matching counterpart (check for counterpart). If not, return invalid. If yes, take that open bracket out from the stack, move on.

After checking all elements in the string, check if there’s something left in the stack (check the number of brackets).

For this problem, we can simply use a list to act like a stack. When we see an open bracket, append that to the stack. When we see a close bracket, pop from the end of the list (or top of the stack) and compare. At the end, do a len(stack) and see if it equals to 0.

def isValid(s):
    # the problem told us we only need to worry about these 3 types
    paran_mapper = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    stack = []
    for b in s:
        if b in paran_mapper:  # see an open bracket, add to stack
            stack.append(b)
        else:
            if not stack:  # more close bracket than open, return invalid
                 return False
            if b != paran_mapper[stack.pop()]:  # close bracket cannot find a matching counterpart, return invalid
                return False
     return len(stack) == 0  # if there's something in the stack, we have more open bracket than close bracket, return invalid

What’s the time complexity for this approach?

def isValid(s):
    paran_mapper = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    stack = []
    for b in s:  # O(n)
        if b in paran_mapper:  # O(1), open_brackets is constant length
            stack.append(b)
        else:
            if not stack:  # O(1)
                 return False
            if b != paran_mapper[stack.pop()]:  # O(1), pop takes constant time
                return False
     return len(stack) == 0  # O(1)

This is good. The total time complexity is O(n) as we go through the string once only.

O(n) is actually the best we can do, as we need to go through the string at least once to check what’s in the string. This solution is also the most popular among people who post on Leetcode. Frankly, this is the solution you want to use.

But for the sake of the discussion, let’s take a look of another solution posted on Leetcode. It’s not using the best approach, but it’s an interesting approach.

Link here

This approach uses the idea that, at some point of string, we WILL see a matching open and close brackets next to each other. This condition has to be true for us to have a chance of a valid string. So the poster, wuyi365, checks for these three types of brackets:

while '()' in s or '{}' in s or '[]' in s: 

If there is indeed a match, then we replace it with empty string

s = s.replace('{}','').replace('()','').replace('[]','')

Let’s say we have a string {()} , the first attempt will remove () , making the string {}, the second attempt will now find {} and replace them with empty string. Now the string is empty, and we can simply check for return s == ''

It’s clever, but the time complexity goes up to O(N²) because

while '()' in s or '{}' in s or '[]' in s:  # this would take O(n)
    s = s.replace('{}','').replace('()','').replace('[]','')  # replace is another O(n) as it needs to scan the string again

The advantage of this is the memory used is only O(1) as we don’t store anything! Most of time when the memory is not an issue, we don’t need to worry about it, but if the interviewer wants to get tricky and adds memory constraint as a requirement, this can be a valid approach.

Quite honestly, even without the memory constraint, if I see this being used during an interview, I will most likely give this person a thumbs up. It shows that this person thinks about the problem and comes up with an attempt that actually solves the problem. This is when we talk about experience, projects, and some behavior questions to determine if such candidate is truly a fit on the team.

Again, not having the best approach is not the end of the world. Sometimes we just want to see if the candidate can think of A solution and see if he/she can code.

That’s it! Another problem down!

Buy my a coffee: https://www.buymeacoffee.com/jonathanckz