Python实现有效括号判定触发Time Limit Exceeded报错排查

题目重述 #

给定仅包含(、)、{、}、[、]的字符串s，判定输入是否为有效括号字符串。有效字符串需满足两个条件：

• 左括号必须由相同类型的右括号闭合
• 左括号必须以正确的顺序闭合

原有实现思路 #

原思路先判断输入是否为空，为空直接返回True；核心假设是所有有效括号字符串必然存在相邻的()、[]或{}子串，因此循环移除这类相邻匹配的括号对，直到字符串为空则判定有效返回True，若无法再找到可移除的匹配对则判定无效返回False。

原有问题代码 #

class Solution:
    def isValid(self, s: str) -> bool:
        l = ['()','[]','{}']
        while s != '':
            while l[0] in s or l[1] in s or l[2] in s:
                try:
                    s.replace(s[s.index(l[0])],'')
                except:
                    ValueError
                try:
                    s.replace(s[s.index(l[1])],'')
                except:
                    ValueError
                try:
                    s.replace(s[s.index(l[2])],'')
                except:
                    ValueError
                continue
            return False
        return True

超时与代码缺陷说明 #

1. 直接导致死循环的语法错误：Python中字符串是不可变对象，str.replace()方法不会修改原字符串，只会返回替换后的新字符串。原代码从未将替换结果赋值回变量s，导致s的值自始至终没有变化，内层while循环的判断条件永远为真，程序陷入无限空转，必然触发超时。
2. 替换逻辑完全错误：即使修正赋值问题，s[s.index(l[0])]取到的是匹配到的括号对的第一个字符（比如匹配到()时，取到的是单个字符(），调用replace会把字符串中所有该字符全部删除，而非仅删除相邻匹配的那一对括号，逻辑完全不符合预期。
3. 无效的异常处理：内层循环的进入条件已经确认三个括号对至少有一个存在于字符串中，str.index()根本不会抛出ValueError；就算抛出异常，代码中仅写了ValueError关键字，没有做任何捕获后的处理逻辑，属于完全无效的代码。
4. 思路本身的效率缺陷：就算修正上述所有语法和逻辑错误，循环删除相邻括号对的思路最坏时间复杂度为O(n²)（例如长度为2n的全嵌套括号((((...))))，需要执行n轮遍历替换，每轮都要扫描整个字符串），当输入字符串长度较大时，依然有超时风险。

最优解法：栈实现 #

栈是括号匹配类问题的标准解法，仅需一次遍历，时间复杂度O(n)，空间复杂度O(n)，性能远高于循环替换思路。

实现逻辑 #

• 前置剪枝：如果字符串长度为奇数，直接返回False——有效括号的长度必然是偶数，无需后续判断。
• 建立右括号到对应匹配左括号的哈希映射，遇到右括号时可以O(1)时间查到应该匹配的左括号类型。
• 遍历字符串：
  • 遇到左括号直接压入栈中；
  • 遇到右括号时，先检查栈是否为空（为空说明没有对应左括号，直接无效），再弹出栈顶元素，判断是否和当前右括号匹配，不匹配直接返回False。
• 遍历完成后，栈为空说明所有括号都完成匹配，返回True；栈不为空说明存在未闭合的左括号，返回False。

正确实现代码 #

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        match_map = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        stack = []
        for c in s:
            if c in match_map:
                if not stack or stack.pop() != match_map[c]:
                    return False
            else:
                stack.append(c)
        return len(stack) == 0

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