LeetCode Valid Parentheses 有效括号问题解题逻辑求教

首先明确题目要求的有效括号需满足3个核心规则：

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

你此前的代码逻辑仅判断相同字符是否连续出现，完全不符合上述规则，例如((会被误判为有效，但实际只有()才符合配对要求，类似([])的嵌套场景也完全无法处理。

标准解法思路 #

该题的经典解法是利用栈的“后进先出”特性处理顺序匹配和嵌套场景，核心执行步骤如下：

1. 预先构建右括号到对应左括号的映射字典，方便遇到右括号时快速查找对应匹配的左括号
2. 初始化空栈，用于存储遍历过程中遇到的左括号
3. 遍历字符串的每一个字符：
   • 如果当前字符是左括号，直接压入栈中
   • 如果当前字符是右括号：
     • 先判断栈是否为空，为空则说明没有对应的左括号可以匹配，直接返回False
     • 弹出栈顶元素，判断是否和当前右括号对应的左括号一致，不一致直接返回False
4. 遍历完成后判断栈是否为空：为空则说明所有左括号都完成匹配，返回True；否则说明存在未匹配的左括号，返回False

可通过测试的实现代码 #

class Solution(object):
    def isValid(self, s):
        # 右括号到对应左括号的匹配映射
        match_map = {')': '(', ']': '[', '}': '{'}
        stack = []
        for char in s:
            # 左括号直接入栈
            if char not in match_map:
                stack.append(char)
            else:
                # 右括号做匹配校验
                if not stack or stack.pop() != match_map[char]:
                    return False
        # 遍历完成后栈为空才说明所有括号都匹配成功
        return not stack

内容的提问来源于stack exchange，提问作者CuriousDolphin