Python Programming Challenge 13: Check for Valid Parentheses using Python

Today, we are back with another Python Programming Challenge from Leetocde: https://leetcode.com/problems/valid-parentheses/.

The Challenge

This challenge requires us to write a function called isValid() that accepts a string containing just the characters '(', ')', '{', '}', '[' and ']'. The function needs to determine if the input string is valid.

An input string is valid if opening brackets are closed by the same type of brackets.

In other words, '(' must be closed by ')', '[' closed by ']' and '{' closed by '}'.

Each closing bracket must be used to close the most recent unclosed opening bracket.

For instance, an input string like '{[]}' is valid as ']' closes '[' and '}' closes '{'.

An input string like '([)]', on the other hand, is invalid as ')' does not close the most recent opening bracket '['.

Expected Results

To test your function, you can run the statements below:

a = '()()[]{}()'
b = '{[()]}'
c = '(()]'
d = ')'
e = '(]{)'
f = '(()'

print(isValid(a))
print(isValid(b))
print(isValid(c))
print(isValid(d))
print(isValid(e))
print(isValid(f))

You should get the following output:

True
True
False
False
False
False

Suggested Approach

Using a stack

An easy way to approach this challenge is to use a stack.

To understand why this is so, think of a stack of plates; the last plate added to the stack is the first plate to be removed.

This order of events – last in first out – is very useful for today’s challenge.

We can iterate through the input string and check if each character is an opening bracket.

If it is, we add it to a stack. Suppose the stack is called openingBrackets.

We keep doing this until we encounter a character that is not an opening bracket (i.e. it is a closing bracket).

When that happens, we need to check if this closing bracket is the correct closing bracket for the most recent opening bracket.

To do that, we remove the most recent item from the openingBrackets stack and use that to determine the correct closing bracket.

If the current bracket is the correct closing bracket, all is good. On the other hand, if it is not, we know that the input string is invalid. Hence, we return False and exit the function.

After iterating through the entire input string, if we have yet to return False, it means all closing brackets have been matched with the correct opening bracket.

However, that does not mean the input string is definitely valid. For instance, an input string like '{([])' will also not cause us to return False. This is because both closing brackets in the string (']' and ')') are matched correctly to their respective opening brackets. However, there is an additional opening bracket ('{') that is not matched.

To check for such a case, we need to ensure that the openingBrackets stack is empty after we finish iterating through the input string.

Got it?

The diagram below shows two examples of how this approach works:

Based on the approach described above, try working on today’s challenge yourself.

You need to figure out how to determine if the current character is an opening bracket. You’ll also need to figure out how to determine the correct closing bracket for each opening bracket.

How to implement a stack in Python?

To implement a stack in Python, you can use a list. To add an element to the stack, use the append() method. To remove the most recently added element, use the pop() method.

The pop() method accepts an optional argument – the index of the element to be removed – and returns the element removed.

If the index provided is out of range, it throws an IndexError exception. If the argument is not provided, it removes the last element.

Let’s look at some examples:

myStack = []
removed = ''

myStack.append('a')
myStack.append('b')
myStack.append('c')

print('Original Stack')
print(myStack)

print('\nRemove element at index 1')
removed = myStack.pop(1)
print('Removed item = ', removed)
print('Resulting stack = ', myStack)

print('\nRemove last element')
removed = myStack.pop()
print('Removed item = ', removed)
print('Resulting stack = ', myStack)

print('\nRemove last element again')
removed = myStack.pop()
print('Removed item = ', removed)
print('Resulting stack = ', myStack)

Here, we first use the append() method to add three elements to myStack.

Next, we pass 1 as argument to the pop() method. This removes the element at index 1 (on line 12) from myStack.

After removing this element, we use the pop() method twice to remove the last two elements from the stack.

If you run the code above, you’ll get the following output:

Original Stack
['a', 'b', 'c']

Remove element at index 1
Removed item =  b
Resulting stack =  ['a', 'c']

Remove last element
Removed item =  c
Resulting stack =  ['a']

Remove last element again
Removed item =  a
Resulting stack =  []

Suggested Solution

Here’s the suggested solution for today’s challenge:

def isValid(s):
    pairs = {'(':')', '[':']', '{':'}'}
    length = len(s)
    openingBrackets = []    
    
    for i in range(length):
        if s[i] in pairs:
            openingBrackets.append(s[i])
        elif len(openingBrackets) == 0:
            return False
        elif pairs[openingBrackets.pop()] != s[i]:
            return False  
            
    if len(openingBrackets) > 0:
        return False
    else:
        return True