Python中的括号问题。在最短的时间和空间内求解？

Question

我正在努力解决这个问题 ^python中的{a1}

其显示时间超过误差。谁能告诉我如何降低时间复杂度？ 这是我的密码：

def findBalanced(expr):

    stack = []
    for char in expr:
        if char in ['(']:
            stack.append(char)
        else:
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == '(':
                if char != ')':
                    return False
           

    if stack:
        return False
    return True

if __name__ == '__main__':
    expr = input()
    count = 0
    for x in range(len(expr)):
        expr = expr[1:] + expr[0]
        if findBalanced(expr):
            count +=1
        else:
            pass
    print(count)

如何用最小的时间和最小的空间来解决这个问题

Answer 1

def solve(s):
    p=0
    t=0
    res = 0
    for i in s:
        if(i=='('):
           
            p+=1
           
        else:
          
            p -= 1
          
        if (p<t):
            print(f"Values of p and t are {p} and {t}")
            t=p
            res = 0
        if(t==p):

            res+=1
            
    if p:
        return 0
    else:
        return res
s= input()
print(solve(s))

Answer 2

我建议在开头添加行print(stack)或for循环。然后在几个示例输入上执行算法。你可能会注意到一些奇怪的事情

请花一点时间去做，试着找出它有什么奇怪之处。这将为您提供如何改进算法的灵感

是你干的吗？在完成之前，请不要再读下去

这个答案的其余部分假设您已经在for循环的开头添加了print(stack)，并且您已经在几个输入示例中查看了输出，并且您已经尝试注意到关于输出的一些令人惊讶的事情。请在阅读此答案的其余部分之前完成此操作

您的算法维护一个堆栈，但是如果您在每次迭代时输出堆栈，您会注意到：堆栈只包含字符(的副本。没有别的了。这是因为stack.append(char)的唯一出现处就在if char in ['(']:的正下方，因此您只会添加(

所以实际上，这个堆栈中包含的唯一信息是它包含了多少(。不需要实际维护堆栈，只需维护一个计数器，即，一个整数，告诉您如果有堆栈，堆栈上将有多少(

用depth = 0替换stack = []，然后用depth += 1替换stack.append(char)，用depth -= 1替换stack.pop()

您的检查if current_char == '(':一点用处都没有，因为堆栈上的字符都是(，所以检查总是正确的，因此是多余的

我将让您计算出计数器的哪些值应该返回true，哪些值应该返回false。祝你好运