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.

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

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).
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