题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

我的解法

这个题目Failed了很多次，主要用list模拟了栈的方法。首先可以通过直接判断整个字符串的长度进行第一轮检测，一开始没有考虑到直接进右括号的情况，后续加入了每次判断栈是否为空。

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == "":
            return True
        stack=[]
        d={'(':1, '[':2, '{':3, ')':4, ']':5, '}':6}
        if len(s) % 2:
            return False
        for item in s:
            if d[item] <=3:
                stack.append(d[item])
            elif stack == []:
                return False
            elif d[item] == 3+stack[-1]:
                stack.pop()
        return stack == []

最优解法

也是类似栈的思想，只是简化了判断条件，有趣的是将一对括号中的一个作为Key，一个作为Value。

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a = {')':'(', ']':'[', '}':'{'}
        l = [None]
        for i in s:
            if i in a and a[i] == l[-1]:
                l.pop()
            else:
                l.append(i)
        return len(l)==1