20.有效的括号

问题描述

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

有效字符串需满足

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

例如：

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

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

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

即左右括号必须是闭合的。

解题思路

使用栈结构来处理这个问题非常简单。

我们从左到右依次扫描字符串的每一个字符，如果是([{左括号就入栈，如果是)]}右括号就从栈里弹出栈顶的元素，然后匹配该字符和栈顶元素是否是成对的。

例如扫描到字符(,然后栈顶元素是),则成对，否则不成对则返回False

扫描完字符串，如果栈里没有元素则说明括号都是成对的，匹配成功。

class Solution:
    def isValid(self, s: str) -> bool:
        # 字符串匹配成功的话其长度一定是偶数, 否则一定不成功
        # 这里可以先检查长度, 可以省略之后的步骤
        if len(s) % 2 != 0:
            return False

        # 辅助栈
        _stack = []
        # 对照表
        _map = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        for _char in list(s):
            if _char in "([{":
                _stack.append(_char)
            else:
                # 当遇到右括号时, 从栈顶弹出元素检测是否
                # 成对, 即是否闭合, 不成对则返回 False
                if _stack:
                    if _char in _map:
                        _top = _stack.pop()
                        if _map[_char] != _top:
                            return False
                else:
                    # 右括号溢出
                    return False
        # 这里要判断栈里是否还有元素
        # 有元素则说明该字符串匹配不成功
        return len(_stack) == 0

原链接

https://leetcode.cn/problems/valid-parentheses/