Weekly Coding Blog: Valid Parentheses – written in Python using stack data structure

Posted by

Hello readers! It’s really important for me to continue my practice and learning. Every week, I block off 30 minutes, set a timer and choose a challenge from leetcode. This helps me keep my skills sharp, see how other devs all over the planet would solve these problems, and take some leisure time to problem solve and be creative. Being able to see other solutions expands my mind for solving future problems in a clever and efficient way. Today, the problem set focuses on Python.

Also, for more on stack data structure in Python, you can access some really cool infographics and information here.

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.
class Solution:
    def isValid(self, s: str) -> bool:

        # create a mapping of characters in open bracket as key and close as value
        charMapping = {
            "(": ")",
            "{": "}",
            "[": "]"
        }
        
        # generate an empty array
        stack = []
        
        for char in s:
            if charMapping.get(char) != None: # if the map returns something
                # we know its an opening bracket
                stack.append(char)
            else:
                # we know its a closing bracket
                last_value = stack.pop() if stack else '' # get the last open value from stack
                if charMapping.get(last_value, '') != char: # check map, default to blank if not found
                    return False
        return True if not stack else False # ternary for stack array

All solutions are also now on my GitHub profile if you want to check out all of the coding challenges I’ve completed so far!

All credit to problem sets goes to Leetcode

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s