时间戳

首页 > 解决方案 > 递归超过时间限制，适用于 90/91 测试用例，在大输入时失败

python - 递归超过时间限制，适用于 90/91 测试用例，在大输入时失败

问题描述

LeetCode 问题 20 - 有效括号。如果输入字符串为“有效”，则返回真。

  1. 开括号必须用相同类型的括号闭合。
  2. 开括号必须以正确的顺序闭合。

代码通过了 90/91 个测试用例，但超过了最后一个用例的时间限制，输入字符串约为 7000 个字符。函数是递归的，所以我尝试导入 sys 来手动增加递归限制 - 没有成功。对此错误非常好奇 - 谢谢！

class Solution(object):
def isValid(self, s):
    import sys
    sys.setrecursionlimit(10**6) 

    #recursion base case
    def base(s):
        return True if len(s) == 0 else False
        
    open = ['(', '[', '{']
    close = [')', ']', '}']
    pairs = zip(open, close)
    
    #function to return true for open/close adjacent pair
    def isPartner(s):            
        return True if s[0] in open and s[1] in close and open.index(s[0]) == close.index(s[1]) else False
    
    if len(s) == 1:
        return False        
    
    if len(s) == 2:
        return isPartner(s)
    
    for i, j in enumerate(s):
        if all(j not in open for j in s) or all(j not in close for j in s):
            return False
        elif isPartner(j + s[i+1]):
            s1 = s.replace(j + s[i+1], '', 1)
            return True if base(s1) else self.isValid(s1)
        elif s[i+1] in open:
            continue
        else:
            return False

标签： pythonrecursion

解决方案

您的递归算法正在分配大量中间字符串。一个更简单的算法是按顺序遍历字符串，检查无论何时找到右括号，它是否与左括号正确匹配。

使用列表作为堆栈来保存所有尚未关闭的左括号。每当你得到一个右括号时，你从堆栈中弹出最后一个括号并检查它们是否匹配。

class Solution:

    def isValid(self, s):
        open_brackets = ['(', '[', '{']
        close_brackets = [')', ']', '}']
        partners = dict(zip(close_brackets, open_brackets))
        bracket_stack = []
        
        for c in s:
            if c in open_brackets:
                bracket_stack.append(c)
            elif c in close_brackets:
                if len(bracket_stack) == 0: # no previous opening bracket
                    return False
                prev = bracket_stack.pop()
                if prev != partners[c]: # non-matching brackets
                    return False

        return len(bracket_stack) == 0 # True if all opening brackets have been popped

推荐阅读