# Valid Parentheses (Python)

## Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', … Read more Valid Parentheses (Python)

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.

Check it out: https://leetcode.com/problems/valid-parentheses/

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:

`class Solution:    def isValid(self, s: str) -> bool:        if len(s) % 2 != 0:            return False        dict = {'(' : ')', '[' : ']', '{' : '}'}        stack = []        for iin s:            if i in dict.keys():                stack.append(i)            else:                if stack == []:                    return False                a = stack.pop()                if i!= dict[a]:                    return False        return stack == []`

Explanation:

Here we use stack validation and a dictionary! We need a Stack to store the last valid left part of the parentheses, the left parentheses are also taken as the key, and their values would be its right parentheses. So if we store the left parentheses inside the stack, and if we find a valid right part, pop it out of the stack. Think about the case ‘{[]}’, it is not hard to figure out, we need a Stack to store the last valid left part of parentheses, when next char is the valid right part, pop out the left part.

Another validation is to check if the length of the string is even, if it is odd, then it's obviously not a valid parenthesis (or) balanced parentheses! so a valid parentheses string’s length should always be even, we can add a check at the beginning. The worst-case scenario is when someone starts off the input as a ‘((((((((((‘ and so on.

GitHub 