【Leetcode刷题Python】括号匹配问题

2022年9月秋招算法工程师笔试题

1 题目

括号匹配问题

定义一个括号串的权值为，它的最长合法括号子序列的长度，例如()())的权值是4，因为它的最长合法括号子序列为()(),求一个给定括号串的所有子串权值之和。

注意，我忘了题目，自己理解的题意是，先求一个字符串的所有子串，并计算子串的权值（即最长合法括号子序列）

并且，权值的计算，我忘记了，不确定是否是这么计算的，我记得的题目给中())())的权值是4。我理解不通。我把题目改成了()())。

我的这种方法，应该算法效率很低，没有在线上运行过

2 python实现

from itertools import combinations
# 求最长合法括号子序列的长度，即权值
def Process(s):
    # resl记录最长合法子串的长度
    w = 0
    stack = list()
    for i in range(len(s)):
        if stack and s[i] == ")" and s[stack[-1]] == "(":
            stack.pop()
        # 将当前的右括号加入到栈中, 可以充当分割的作用
        else:
            stack.append(i)
        # 栈非空的时候更新当前的长度, 说明已经匹配完所有的左括号了
        if stack:
            r = i - stack[-1]
        else:
            # 说明当前的左括号已经全部消除掉了
            r = i + 1
        # 合法序列的长度更大则更新, 相等则数目加1
        if r > w:
            w = r
    return w
# 生成所有子串
def generate_s(s):    
    substring = []
    for i in range(1,len(s)+1):
        substring.extend(list(combinations(s,i)))
    substring = [''.join(i) for i in substring]
    return substring
if __name__ == '__main__':
    s = '()()())'
    score = 0
    for i in generate_s(s):
        score +=Process(s)
    print(score)