Valid Parentheses (via Leetcode)¶

Date published: 2020-03-14

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, stack

This example was found on Leetcode.

I'll extensively walk through how I'd solve this problem.

Problem statement¶

You're given a string containing just the following characters: "(", ")", "{", "}", "[", "]". Determine if the input string is valid.

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

Test cases¶

Test case #1:

• Input: "[]"
• Output: True
• Reasoning: The open bracket is closed by the same type of bracket in the correct order.

Test case #2:

• Input: "[{]}"
• Output: False
• Reasoning: The first closing bracket of "]" closes that type out before the a previous "[" needed to be closed first. Open brackets are not closed in the correct order.

Test case #3:

• Input: "({}]"
• Output: False
• Reasoning: The open bracket of "(" is never closed. There's a closing bracket of "[" but that doesn't match.

Test case #4:

• Input: "[[{}]]"
• Output: True
• Reasoning: All open brackets are closed by the same type of brackets and in the correct order.

I can write out assert statements in Python for these 4 test cases and the empty string consideration one.

In [1]:

# assert valid_parentheses("[]") == True

# assert valid_parentheses("[{]}") == False

# assert valid_parentheses("({}]") == False

# assert valid_parentheses("[[{}]]") == True

# assert valid_parentheses("") == True

# assert valid_parentheses("[]") == True # assert valid_parentheses("[{]}") == False # assert valid_parentheses("({}]") == False # assert valid_parentheses("[[{}]]") == True # assert valid_parentheses("") == True

Logic for Solution¶

I will have to examine every element in the input string. Therefore, I should iterate over it. A string is a Python sequence that allows for iteration over every element.

When I think about the input "[{]}", I know that every successive open bracket must be closed by the same type before an earlier open bracket is closed. Let me write out a few step-by-step examples on how I'd solve this.

One data structure that comes to mind here is a stack. A stack stores elements in what seems like a list, but it is optimized by time complexity for operations by last-in-first-out - aka "LIFO" - and first-in-first-out - aka "FIFO".

A stack optimized data structure in Python is found in the collections package and deque module. For a deque, use the append method to insert an element into the end of the structure and pop to remove an element from the end of the structure.

Operations for "[{]}":

1. Iterate over element "[". Since it's an open bracket, append to deque b/c open bracket.
2. Iterate over "{". Since it's an open bracket, append to deque b/c open bracket.
3. Iterate over "]". Since it's a closed bracket, compare this to the last item in the deque. This element is a different type than the last item in the deque. Therefore, return False.

Operation for "[[{}]]":

1. Iterate over element "[". Since it's an open bracket, append to deque b/c open bracket.
2. Iterate over element "[". Since it's an open bracket, append to deque b/c open bracket.
3. Iterate over element "{". Since it's an open bracket, append to deque b/c open bracket.
4. Iterate over element "}". Since it's a closed bracket, compare this to the last item in the deque. This is element is the same type as the last item in the deque. Pop out last item added to deque.
5. Iterate over element "]]". Since it's a closed bracket, compare this to the last item in the deque. This is element is the same type as the last item in the deque. Pop out last item added to deque.
6. Iterate over element "]". Since it's a closed bracket, compare this to the last item in the deque. This is element is the same type as the last item in the deque. Pop out last item added to deque.
7. Return True

This pseudocode generally explains the step logic.

In [2]:

# from collections import deque

# create a function with string as an input
    # create an empty deque
    # create dict in which keys are open brackets and values are of the same type closed brackets

    # iterate over each character in input string
        # if it's an open bracket
            # append item to deque
            
        # else if it's a closed bracket and there are no brackets in our stack
            # we can't add a closed bracket as the first in our stack b/c it's invalid
            # return False
        # else:  # it's a closed bracket
            # if this closed type is the same as the last open type in the stack
                # pop out last item in deque
            # else:
                # this is the wrong match so return False to break out of function
    # finished iteration...
    # if length of deque is 0 meaning all open brackets have been closed properly
        # return True
    # else:  # there are open brackets that haven't been closed
        # return False

# from collections import deque # create a function with string as an input # create an empty deque # create dict in which keys are open brackets and values are of the same type closed brackets # iterate over each character in input string # if it's an open bracket # append item to deque # else if it's a closed bracket and there are no brackets in our stack # we can't add a closed bracket as the first in our stack b/c it's invalid # return False # else: # it's a closed bracket # if this closed type is the same as the last open type in the stack # pop out last item in deque # else: # this is the wrong match so return False to break out of function # finished iteration... # if length of deque is 0 meaning all open brackets have been closed properly # return True # else: # there are open brackets that haven't been closed # return False

Code¶

In [3]:

from collections import deque
import logging

logging.basicConfig(level=logging.DEBUG, format='%(asctime)-25s %(levelname)-7s %(lineno)-4s %(message)-8s')                      


def valid_parentheses(brackets_string):
    """
    Compute if a string is a valid parentheses string such as "{}" or "{[[]]}"
    
    param brackets_string: the string to validate if it's a valid parentheses
    return boolean: True if brackets_string is a valid parentheses
    """

    logging.debug("assign empty deque to open_brackets_stack...")
    open_brackets_stack = deque()

    logging.debug("create dict in which keys are open brackets and values are of the same type closed brackets")
    bracket_pair_dict = {'[': ']',
                         '{': '}',
                         '[': ']'
                        }
    
    logging.debug("iterate over each character in input string...")
    for bracket in brackets_string: 
        logging.debug(f"bracket: {bracket}")
        logging.debug("check if bracket is an open type...")
        if bracket in bracket_pair_dict:
            logging.debug("append bracket to stack...")
            open_brackets_stack.append(bracket)
        elif bracket not in bracket_pair_dict and len(open_brackets_stack) == 0:
            logging.debug("closed bracket can't be the first item in a valid stack...")
            return False
        else:
            logging.debug("under this condition we have a closed bracket and there are items in the stack...")
            logging.debug(f"{bracket} is a closed bracket...")
            logging.debug("check if this closed type is the same as the last open type in our stack...")
            last_open_in_stack = open_brackets_stack[-1]
            logging.debug(f"last_open_in_stack: {last_open_in_stack}")
        
            if bracket_pair_dict[last_open_in_stack] == bracket:
                logging.debug("we have a match of same open and closed type...")
                logging.debug("pop out last item in stack...")
                open_brackets_stack.pop()
            else:
                logging.debug("we have a mismatch of the open and closed type...")
                return False
            
    logging.debug("loop has finished...")
    if len(open_brackets_stack) == 0:
        logging.debug("length of stack is 0 so all open brackets have been closed in proper order...")
        return True
    else:
        logging.debug("still open brackets in the so they haven't been properly closed...")
        return False

from collections import deque import logging logging.basicConfig(level=logging.DEBUG, format='%(asctime)-25s %(levelname)-7s %(lineno)-4s %(message)-8s') def valid_parentheses(brackets_string): """ Compute if a string is a valid parentheses string such as "{}" or "{[[]]}" param brackets_string: the string to validate if it's a valid parentheses return boolean: True if brackets_string is a valid parentheses """ logging.debug("assign empty deque to open_brackets_stack...") open_brackets_stack = deque() logging.debug("create dict in which keys are open brackets and values are of the same type closed brackets") bracket_pair_dict = {'[': ']', '{': '}', '[': ']' } logging.debug("iterate over each character in input string...") for bracket in brackets_string: logging.debug(f"bracket: {bracket}") logging.debug("check if bracket is an open type...") if bracket in bracket_pair_dict: logging.debug("append bracket to stack...") open_brackets_stack.append(bracket) elif bracket not in bracket_pair_dict and len(open_brackets_stack) == 0: logging.debug("closed bracket can't be the first item in a valid stack...") return False else: logging.debug("under this condition we have a closed bracket and there are items in the stack...") logging.debug(f"{bracket} is a closed bracket...") logging.debug("check if this closed type is the same as the last open type in our stack...") last_open_in_stack = open_brackets_stack[-1] logging.debug(f"last_open_in_stack: {last_open_in_stack}") if bracket_pair_dict[last_open_in_stack] == bracket: logging.debug("we have a match of same open and closed type...") logging.debug("pop out last item in stack...") open_brackets_stack.pop() else: logging.debug("we have a mismatch of the open and closed type...") return False logging.debug("loop has finished...") if len(open_brackets_stack) == 0: logging.debug("length of stack is 0 so all open brackets have been closed in proper order...") return True else: logging.debug("still open brackets in the so they haven't been properly closed...") return False

In [4]:

assert valid_parentheses("[]") == True

assert valid_parentheses("[]") == True

2020-03-14 18:12:04,558   DEBUG   9    assign empty deque to open_brackets_stack...
2020-03-14 18:12:04,559   DEBUG   12   create dict in which keys are open brackets and values are of the same type closed brackets
2020-03-14 18:12:04,561   DEBUG   18   iterate over each character in input string...
2020-03-14 18:12:04,562   DEBUG   20   bracket: [
2020-03-14 18:12:04,563   DEBUG   21   check if bracket is an open type...
2020-03-14 18:12:04,564   DEBUG   23   append bracket to stack...
2020-03-14 18:12:04,566   DEBUG   20   bracket: ]
2020-03-14 18:12:04,567   DEBUG   21   check if bracket is an open type...
2020-03-14 18:12:04,569   DEBUG   29   under this condition we have a closed bracket and there are items in the stack...
2020-03-14 18:12:04,570   DEBUG   30   ] is a closed bracket...
2020-03-14 18:12:04,570   DEBUG   31   check if this closed type is the same as the last open type in our stack...
2020-03-14 18:12:04,571   DEBUG   33   last_open_in_stack: [
2020-03-14 18:12:04,572   DEBUG   36   we have a match of same open and closed type...
2020-03-14 18:12:04,573   DEBUG   37   pop out last item in stack...
2020-03-14 18:12:04,574   DEBUG   43   loop has finished...
2020-03-14 18:12:04,575   DEBUG   45   length of stack is 0 so all open brackets have been closed in proper order...

Turn off logging messages for the rest of the test cases.

In [5]:

logger = logging.getLogger()
logger.disabled = True

logger = logging.getLogger() logger.disabled = True

In [6]:

assert valid_parentheses("[{]}") == False

assert valid_parentheses("({}]") == False

assert valid_parentheses("[[{}]]") == True

assert valid_parentheses("") == True

assert valid_parentheses("[{]}") == False assert valid_parentheses("({}]") == False assert valid_parentheses("[[{}]]") == True assert valid_parentheses("") == True