LeetCode-J-栈-20. 有效的括号

fishni

数据结构与算法

发布于：2021年5月13日

栈、括号匹配

题目

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

有效字符串需满足：

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

示例1：

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

示例2：

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

题解

思路分析：采用栈数据结构，当出现左括号时，就将其入栈，当出现右括号时判断栈顶是否为其对应左括号，若是，则将左括号出栈；否则，返回false，直至栈空则返回true
注意：当字符串长度为奇数时，直接返回False

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2==1:
            return False
        
        
        pairs= {"}":"{",")":"(","]":"["}
        stack=list()
        for c in s:
            if c in pairs:
                if not stack or stack[-1]!=pairs[c]:
                    return False
                stack.pop()
            else:
                stack.append(c)
        return not stack