20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Solution: Stack

BRACKETS = {
    ('(', ')'), 
    ('[', ']'), 
    ('{', '}')
}


class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for char in s:
            if stack and (stack[-1], char) in BRACKETS:
                stack.pop()
            else:
                stack.append(char)
        return stack == []