# Valid Parentheses — Day 7(Python)

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.

## More from Annamariya Tharayil

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