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来求解

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        amap = {")": "(", "]": "[", "}": "{"}
        astack = []
        for i in s:
            if i not in amap:
                astack.append(i)
            else:
                if not astack or astack.pop() != amap.get(i):
                    return False
        return not astack