[ LeetCode ] 题刷刷(Python)-第20题：有效的括号

题目描述

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

有效字符串需满足：

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

示例

示例 1：

输入：s = "()"
输出：true
示例 2：

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

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

解题

解法一： 栈辅助法

思路

利用栈数据结构的特点（后进先出，LIFO）来模拟括号的匹配过程，确保遇到的每一个右括号都能找到对应的左括号。

1. 遍历字符串：从左到右逐个遍历字符串中的每一个字符。
2. 使用栈存储左括号：每当遇到一个左括号（如 '(', '[', or `'{``）时，将其压入栈中。栈用于暂存未匹配的左括号。
3. 检查右括号与栈顶左括号的匹配性：当遇到一个右括号（如 ')', ']', or '}'）时，检查栈是否为空以及栈顶元素是否与当前右括号匹配。若栈非空且栈顶元素与当前右括号匹配，则弹出栈顶元素；否则，字符串无效，返回 False。
4. 遍历结束后的判断：遍历完整个字符串后，若栈为空，说明所有左括号都已经找到对应的右括号，字符串有效，返回 True；否则，栈中仍有未匹配的左括号，字符串无效，返回 False。

算法复杂度

时间复杂度：O(n)，其中 n 为字符串 s 的长度。

由于函数对字符串 s 中的每个字符均进行一次操作，因此，该函数的时间复杂度为 O(n)，其中 n 为字符串 s 的长度。

空间复杂度：O(n)，其中 n 为字符串 s 的长度。

函数使用了一个栈 stack 存储遍历过程中遇到的左括号。在最坏情况下，即字符串 s 中的所有括号都是有效配对的，栈中最多存储与字符串长度相等的左括号。

代码

class Solution:
    def isValid(self, s: str) -> bool:
        # 定义一个字典，用于映射左括号到对应的右括号
        opening_brackets = {'(': ')', '[': ']', '{': '}'}

        # 初始化一个空栈，用于存储遇到的左括号
        stack = []

        # 遍历输入字符串中的每一个字符
        for char in s:
            # 当前字符为左括号时，将其压入栈中
            if char in opening_brackets:
                stack.append(char)

            # 当前字符为右括号，且栈非空且栈顶元素与当前右括号匹配时，
            # 弹出栈顶元素（表示找到了一个有效的括号对）
            elif stack and char == opening_brackets[stack[-1]]:
                stack.pop()

            # 当前字符为右括号，但与栈顶左括号不匹配时，字符串无效，提前返回 False
            else:
                return False

        # 遍历完整个字符串后，若栈为空，说明所有左括号都已经找到对应的右括号，字符串有效，返回 True
        # 若栈不为空，说明还有未匹配的左括号，字符串无效，返回 False
        return not stack