# 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:

- Open brackets must be closed by the same type of brackets.
- 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.

- Construct a dictionary that holds opening brackets (value) and closing brackets(key).
- Have a set of opening brackets. A set will help us to identify opening brackets.
- Run the loop for each character in the string, check if it is an opening bracket. If yes, push it into the stack.
- 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.
- If any of the above condition is False, return False
- 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.