0020 - Valid Parentheses - revise

You are given a string s consisting of the following characters: '(', ')', '{', '}', '[' and ']'.

The input string s is valid if and only if:

Every open bracket is closed by the same type of close bracket. Open brackets are closed in the correct order. Every close bracket has a corresponding open bracket of the same type. Return true if s is a valid string, and false otherwise.

Example 1:

Input: s = "[]"

Output: true Example 2:

Input: s = "([{}])"

Output: true Example 3:

Input: s = "[(])"

Output: false

1. Build hasmap with closing bracket as key and opening bracket as value
2. if char not in hashmap (ie it's opening bracket), append it
3. else: a. if stack empty, return false b. else pop top element on stack, if popped element != hasmap[char] then return false
4. if stack empty return true

In [2]:

def isValid(s):
    hashmap = {'}':'{',')':'(',']':'['}
    stack = []
    for i in s:
        if i not in hashmap:    #if i is not closing bracket, then append
            stack.append(i)
        else:
            if not stack:   #empty stack, cannot add closing bracket, return false
                return False
            else:
                popped = stack.pop()
                if popped!=hashmap[i]:  #if popped element is not the opening bracket, return false
                    return False
    return not stack    #stack should be empty for true

In [3]:

isValid("([{}])")

Out[3]:

True

In [ ]: