O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2 == 1:
            return False

        left = ['(', '[', '{']
        d = {')':'(', ']':'[', '}':'{'}

        l = []
        for e in s:
            if e in left:
                l.append(e)
            else:
                if not l or d[e] != l.pop():
                    return False

        if not l:
            return True
        else:
            return False

def main():
    s = Solution()

    print(s.isValid("()")) # True
    print(s.isValid("()[]{}")) # True
    print(s.isValid("(]")) # False
    print(s.isValid("([)]")) # False
    print(s.isValid("{[]}")) # True

if __name__ == '__main__':
    main()