LeetCode有效括号解法出现运行时错误，求问题排查与解析

问题背景 #

给定仅包含(、)、{、}、[和]的字符串s，需判断其是否为有效字符串，有效字符串需满足：

• 开括号必须由相同类型的闭括号闭合
• 开括号必须按正确顺序闭合
• 每个闭括号都有对应的同类型开括号

示例：

• 输入s="()"，输出True
• 输入s="()[]{}"，输出True
• 输入s="(]"，输出False

约束条件：1 ≤ s.length ≤ 10⁴，s仅由()[]{}组成

待排查的Python代码 #

class Solution:
    @staticmethod
    def isBalanced(s):
        dict_mapping = {'}': '{', ')': '(', ']': '['}
        open_stack = []

        for char in s:
            if char in dict_mapping.values():
                open_stack.append(char)
            elif char in dict_mapping.keys():
                if not open_stack or open_stack.pop() != dict_mapping[char]:
                    return False
            else:
                # Handle characters other than parentheses, braces, and brackets
                return False

        return len(open_stack) == 0

问题排查与修正 #

运行时错误核心原因 #

这段代码的逻辑本身是正确的，但如果在在线判题系统（如LeetCode）中提交，方法名不符合题目要求会导致运行时错误——多数OJ要求该题的方法名为isValid，而非isBalanced。

优化后的修正代码 #

同时，为提升查找效率，我们可以将开括号的判断方式从遍历字典值改为集合查找（集合查找时间复杂度为O(1)，比遍历值更高效）：

class Solution:
    def isValid(self, s: str) -> bool:
        dict_mapping = {'}': '{', ')': '(', ']': '['}
        open_stack = []
        open_brackets = {'(', '[', '{'}
        
        for char in s:
            if char in open_brackets:
                open_stack.append(char)
            elif char in dict_mapping:
                if not open_stack or open_stack.pop() != dict_mapping[char]:
                    return False
        
        return len(open_stack) == 0

修正细节说明 #

1. 方法名适配：将原方法名isBalanced改为OJ要求的isValid，并添加类型注解以符合现代Python编码规范
2. 性能优化：用集合open_brackets存储开括号，替换原有的dict_mapping.values()查找，降低循环中的查找开销
3. 冗余代码移除：根据题目约束，输入字符串仅包含括号类型字符，因此无需保留处理其他字符的else分支

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