LeeCode 20. 有效的括号

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

首先明确限定条件,

1.括号必须成对出现

2.左括号永远在右括号之前

3.括号可以整体嵌套但是不能穿插嵌套

因此,要用到一个字典,键为左括号,值为右括号,

还需要一个列表,遍历时,左括号直接放列表中,右括号就把列表中最后一个拿出来比较一下能不能配成一对

最后如果都成对出现了,列表中应该一个值都没有了,但是为了不让列表为空爆出索引错误,要多给字典中添加一个哨兵做后盾

根据思路写出Python3代码

class Solution:
    def isValid(self, s: str) -> bool:
        cp = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for elem in s:
            if elem in cp:
                stack.append(elem)
            elif cp[stack.pop()] != elem:
                return False
        return len(stack) == 1

在《LeeCode 20. 有效的括号》上留下第一个评论