Notes on how to solve the Valid Parentheses problem

This series of post is like my coding diary – a place where I jot down what worked (and what didn’t) so that future-me can have an easier go at it. In this post I’ll take a look at the Valid Parentheses problem

Problem statement

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Examples

Example 1:

Input: s = "()" → Output: true

Example 2:

Input: s = "()[]{}" → Output: true

Example 3:

Input: s = "(]" → Output: false

My thought process

The first thing that comes to mind is to have some sort of memory of the open brackets that I’ve seen so far. If I find a closing bracket, I can check if the last open bracket is of the same type. If it is, I can remove it from the memory and continue. If it isn’t, I can return false.

The best structure for this is of course a stack. We are going to add to the stack every time we find an opening bracket and remove from it every time we find a closing bracket. If the stack is empty when we find a closing bracket, we can return false. If the stack has elements when we finish iterating through the string, we can return false. Otherwise life is good and we return true.

I’ll use a new example for this:

s = "{[()]}"

i = 0
     ↓
    "{[()]}"
    Since { it's an opening bracket
      we add it to the stack → stack = ["{"]

i = 1
      ↓
    "{[()]}"
    Since [ it's an opening bracket
      we add it to the stack → stack = ["{", "["]

i = 2
       ↓
    "{[()]}"
    Since ( it's an opening bracket
      we add it to the stack → stack = ["{", "[", "("]

i = 3
        ↓
    "{[()]}"
    Since ) it's a closing bracket
      we check if the last element of the stack is a matching bracket,
      it is, so we pop it out → stack = ["{", "["]

i = 4
         ↓
    "{[()]}"
    Since ] it's a closing bracket
      we check if the last element of the stack is a matching bracket,
      it is, so we pop it out → stack = ["{"]

i = 5
          ↓
    "{[()]}"
    Since } it's a closing bracket
      we check if the last element of the stack is a matching bracket,
      it is, so we pop it out → stack = []

We finshed iterating through the string and the stack is empty, so we return true.

My solution

class Solution:
  # Using a stack
  def isValid(self, s: str) -> bool:
    stack = []

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

    for char in s:
      if char in matching_brackets.values(): # It's an opening bracket
        stack.append(char)
      else: # It's a closing bracket
        if len(stack) == 0:
          # if we don't have any opening brackets in the stack
          return False
        if stack.pop() != matching_brackets[char]:
          # if the last opening bracket is not of the same type
          return False

    return True

Possible follow-up questions

Can we do it by using a O(1) memory?

If we don’t use a stack, we can use a counter. We can increment the counter every time we find an opening bracket and decrement it every time we find a closing bracket. If the counter is negative at any point, we can return false. If the counter is not zero when we finish iterating through the string, we can return false. Otherwise life is good and we return true.

Since we have three type of parentheses, we need three counters.

class Solution:
  def isValid(self, s: str) -> bool:
    open_parentheses = 0
    open_brackets = 0
    open_braces = 0

    for char in s:
      if char == "(":
        open_parentheses += 1
      elif char == "[":
        open_brackets += 1
      elif char == "{":
        open_braces += 1
      elif char == ")":
        open_parentheses -= 1
      elif char == "]":
        open_brackets -= 1
      elif char == "}":
        open_braces -= 1

      if open_parentheses < 0 or open_brackets < 0 or open_braces < 0:
        return False

    return open_parentheses == 0 and open_brackets == 0 and open_braces == 0

This solution is not as elegant as the previous one, but it’s still O(n) time complexity and O(1) memory complexity.