20_Valid_Parentheses.py

"""
https://leetcode.com/problems/valid-parentheses/

Given a string 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.
Note that an empty string is also considered valid.

Example 1:
    Input: "()"
    Output: true

Example 2:
    Input: "()[]{}"
    Output: true

Example 3:
    Input: "(]"
    Output: false

Example 4:
    Input: "([)]"
    Output: false

Example 5:
    Input: "{[]}"
    Output: true
"""
#stack
class Solution:
    def isValid(self, s: 'str') -> 'bool':
        d = {'(':')', '[':']', '{': '}'}
        stack = []
        if s=='':
            return True
        for i in range(len(s)):
            if s[i] in ['(', '[', '{']:
                stack.append(s[i])
            elif s[i] in [')', ']', '}']:
                if len(stack)==0:
                    return False
                t = stack.pop()
                if d[t]!=s[i]:
                    return False
        if len(stack)==0:
            return True
        else:
            return False
            
x = Solution()
print(x.isValid("()[]"))