Valid Parentheses — Day 7(Python)

Photo by Nathan Dumlao on Unsplash

Today we will be looking into one of Leetcode’s Easy tagged questions. Let us jump into the problem without losing much time.

20. Valid Parentheses

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

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Solution

Since we have a limited set of brackets to worry about in this problem, we can use a dictionary that holds the key as closing brackets and value as a respective opening bracket. We need a stack which will hold the order of opening brackets, we can remove the opening brackets from the stack when we find the right closing bracket.

  1. Construct a dictionary that holds opening brackets (value) and closing brackets(key).
  2. Have a set of opening brackets. A set will help us to identify opening brackets.
  3. Run the loop for each character in the string, check if it is an opening bracket. If yes, push it into the stack.
  4. If the current character is a closing bracket, check if the topmost element in the stack is the right opening bracket for the current closing bracket. If yes, pop the topmost element in the stack.
  5. If any of the above condition is False, return False
  6. Once the entire loop is completed, check for any remaining items in the stack. If the stack is empty return true, else return false.
class Solution:
def isValid(self, s: str) -> bool:
dictionary_brackets = {'}':'{',')':'(', ']':'['}
open_bracket = ('{','(','[')
stack_bracket = []
for each_char in s:
if stack_bracket == [] or each_char in open_bracket:
stack_bracket.append(each_char)
elif(dictionary_brackets[each_char]==stack_bracket[-1]):
stack_bracket.pop()
else:
return False
return False if stack_bracket else True

Complexity analysis

Time Complexity

We would be required to traverse through each character in the string which would take O(N).

Space Complexity

In worst-case-scenario, if our input string is ‘(((([[[[[{{{{’. The entire string will be stored in the stack, which means the space complexity will be O(N).

I would like to improve my writing skills so any suggestions or critiques are highly welcomed.

--

--

--

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Azure CLI is broken Again

Terraform Deployments with Google Cloud Build

A one time reward winning experience with KeplerSwap and its Launch

Little things for a big win Part 1

Multichannel to Open Banking to Data Insights: It All Starts with APIs

Android UT and UI Testing basics Part — 3

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Annamariya Tharayil

Annamariya Tharayil

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

More from Medium

Introduction to Programming - What is Programming Paradigm?

What is Flowchart? How flowchart helps in your Coding Practices ? #Python Series-1

Min-Max Sum(30 Day Hackerrank Challenge)

Play Wordle like a pro with Python

Wordle logo