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

Building a Prototype for a Spotify Peer-to-Peer Automated Playlist Creator Using Python &…

Launch EC2 instance & attach EBS volume using AWS CLI

Is Cloud Computing the goldmine of post-covid era?

Cloud With Chris — Moving Forwards

Cloud with Chris Logo

Command Execution with PostgreSQL Copy Command

Is That Mine, Or….?

Simple match game for children using Flutter

In-House Software vs SaaS: What’s the Difference and Which Is Better?

Cloud vs On-premise DAM and Image Management

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

CaDS— Code and Data Society

Solutions of leetcode question 22: Generate Parentheses

Tower of Hanoi in Python

Pangrams and how I solved it !