【LeetCode20】有效的括号

题目描述

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

有效字符串需满足：

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

思路与算法

1. 栈的使用：
   当我们遍历字符串 s 中的每个字符时：
   • 如果遇到 左括号（‘(’, ‘{’, ‘[’），我们将其压入栈中。
   • 如果遇到 右括号（), }, ]），我们检查栈顶的元素：
     • 如果栈为空，说明没有对应的左括号，返回 False。
     • 如果栈顶元素是对应的左括号（例如，遇到 ) 时，栈顶应该是 ‘(’），则将栈顶元素弹出，继续检查下一个字符。
     • 如果匹配不成功，立即返回 False。
2. 字符串遍历完成后：
   如果栈为空，说明所有的括号都已成功匹配，返回 True。
   如果栈不为空，说明还有未匹配的左括号，返回 False。

代码

class Solution:
    def isValid(self, s: str) -> bool:
        # 初始化一个栈来存储左括号
        stack = []

        # 初始化哈希表，存储括号的配对关系
        bracket_map = {')':'(', '}':'{',']':'['}

        # 遍历
        for char in s:
            # 如果是右括号
            if char in bracket_map:
                # 检查栈顶是否匹配
                top_element = stack.pop() if stack else '#'
                if top_element != bracket_map[char]:
                    return False
            else:
                stack.append(char)
        
        return not stack
        

使用一个哈希表 bracket_map 来存储右括号对应的左括号映射。这样当遇到一个右括号时，我们就可以通过查找哈希表快速获得它对应的左括号 if top_element != bracket_map[char]:

此外，在字典中，in 运算符默认检查的是字典的键，而不是值。

总结

1. 在 Python 中，列表有以下几种方法可以帮助我们模拟栈的行为：
   append(x)：将元素 x 推入栈的顶部（即列表的末尾）。
   pop()：移除并返回栈顶部的元素（即列表的最后一个元素）。
   这两个方法完美地支持栈的基本操作（压栈和弹栈），因此我们可以利用列表来实现栈的功能。
2. 使用栈和哈希表处理括号匹配是常见的技巧.