博客

给定一个只包括

'('

，

')'

，

'{'

，

'}'

，

'['

，

']'

的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

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

示例 3:

输入: "(]"
输出: false

示例 4:

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

示例 5:

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

思路：

处理右括号需要看前面有没有匹配的左括号，所以可以用栈。

每次左括号就压进栈，

右括号就看栈顶是不是匹配的左括号，如果不是说明有问题， 比如 [ )，就无法匹配上，

如果匹配上了，就把栈顶pop掉。

最后判断是不是栈里所有左括号都脱单了。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        mapping = {")":"(", "]":"[", "}":"{"}
        stack = []
        for i, char in enumerate(s):
            if char not in mapping:#left
                stack.append(char)
            else:
                if not stack or stack[-1] != mapping[char]:
                    return False
                stack.pop()
                
        return len(stack) == 0