'Valid Parenthesis' Problem Walk-Through in Python

Introduction

While there are many, many ways to approach this sort of problem, this guide will run down one that I felt was easiest to understand.

Feel free to give this problem a shot yourself before reading ahead!

Problem Statement

Given a string of characters '(', ')', '{', '}', '[' and ']', determine if the string is valid, based on whether all of the parenthesis close by their corresponding pair.

Ex:

• "{ }" = true

• "( )[ ]{ }" = true

• "( ]" = false

• "( [ ]{ } )" = true

Process

As always, start off with pseudocode--a sort of rough sketch of how your program will run:

class Solution:
    def isValid(self, s: str) -> bool:

        # check for even number of elements
        # create a dictionary for each parenthesis pair
       
        # initialize a stack in the form of a list
        # loop over string
        
            # if there is an open parenthesis, add it to the stack
            # if there is a closed parenthesis...
                # and if the stack has one or more elements +
                # the closed parenthesis' pair is at the end of the stack
                # remove that pair
                # if there is an unmatched parenthesis, we can exit
               
        # if the stack is empty, all pairs have been found
        

In short:

• an odd number of elements will always return False because there aren't enough pairs

• we created a dictionary that matches open with closed parenthesis that will help us later

• a stack is just a scary-sounding data structure that boil down to lists operating in a specific way

  • we add open parenthesis to the stack

  • if a closed parenthesis is found and it matches the top-most item in the list / stack, remove or pop that parenthesis from the list

• Finally, if the length of the stack is 0, all pairs have been found and we can exit the program

Now, we can begin filling in the code:

class Solution:
    def isValid(self, s: str) -> bool:

        # check for even number of elements
        strlen = len(s)
        if (strlen % 2 != 0):
            return False

        # matches each closed parenthesis with its open counterpart
        dictPair = {
            '}' : '{',
            ')' : '(',
            ']' : '['
        }

        # initializes a stack in the form of a list
        stack = []
        # loops over string
        for char in s:
            # if there is an open parenthesis, add it to the stack
            if (char in ['{', '(', '[']):
                stack.append(char)
            # if there is a closed parenthesis...
            elif (char in ['}', ')', ']']):
                # and if the stack has one or more elements +
                # the closed parenthesis' pair is at the end of the stack
                # remove that pair
                if (dictPair[char] == stack[-1]):
                    stack.pop(-1)
                # if there is an unmatched parenthesis, we can exit
                else:
                    return False

        # if the stack is empty, all pairs have been found
        if (len(stack) == 0):
            return True
        return False

While this passes most test cases, there yet remains one issue. Where we say...

if (dictPair[char] == stack[-1]):

... we don't quite know that there are elements in the stack, resulting in an indexing error because we attempted to access the last element.

That's why an input such as "}{", that start with a closed parenthesis, would produce an indexing error.

if (stack and dictPair[char] == stack[-1]):

This simple addition of "stack and" ensures that the stack exists and is non-empty!

Final Thoughts

Thanks for reading!