Day18 - 20. 有效的括号

题目链接 ：https://leetcode.cn/problems/valid-parentheses/description/

问题理解：

• 我们需要判断一个只包含括号的字符串是否有效。有效的标准是：

  1. 每种左括号必须用相同类型的右括号闭合

  2. 括号必须按正确的顺序闭合（即后开的括号要先闭合）

  3. 每个右括号都必须有一个对应的左括号

解法思路

使用栈这种"先进后出"的数据结构非常适合解决这个问题：

1. 遇到左括号时，我们把对应的右括号压入栈中（这样后面可以直接比较）

2. 遇到右括号时，检查它是否与栈顶元素匹配

   • 如果匹配，弹出栈顶元素（表示这对括号匹配成功）

   • 如果不匹配，说明括号顺序或类型不对，直接返回false

3. 最后检查栈是否为空

   • 如果栈为空，说明所有括号都正确匹配

   • 如果栈不为空，说明有左括号没有匹配的右括号

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:  #遇到右括号：没有找到左括号或者左括号（栈顶）不是它
                return False
            else: # 匹配成功，弹出栈顶元素
                stack.pop()
            
        return True if not stack else False