【队列 &栈】Leecode-20. 有效的括号

【题目】

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

【题解】

题解1：

• 思路

         遍历字符串，逐个加入栈中，比较最上面两个，如果匹配是一对出栈

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(n)

• 代码

class Solution:
    def isValid(self, s: str) -> bool:
        pp = {
            '(': ')',
            '{': '}',
            '[': ']',
        }
        arr = []
        for i in s:

            if arr and arr[-1] in pp and pp[arr[-1]]== i:
                arr.pop()
            else:
                arr.append(i)
        return False if arr else True