用python计算括号匹配序列最长公共子序列的问题?

网易的笔试题,代码已经写好,但一直无法100%通过测试,找不到问题所在,想请各位大神不吝赐教。

 '''
一个合法的括号匹配序列被定义为:
1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
例如"", "()", "()()()", "(()())", "(((()))"都是合法的。
从一个字符串S中移除零个或者多个字符得到的序列称为S的子序列。
例如"abcde"的子序列有"abe","","abcde"等。
定义LCS(S,T)为字符串S和字符串T最长公共子序列的长度,即一个最长的序列W既是S的子序列也是T的子序列的长度。
小易给出一个合法的括号匹配序列s,小易希望你能找出具有以下特征的括号序列t:
1、t跟s不同,但是长度相同
2、t也是一个合法的括号匹配序列
3、LCS(s, t)是满足上述两个条件的t中最大的
因为这样的t可能存在多个,小易需要你计算出满足条件的t有多少个。

如样例所示: s = "(())()",跟字符串s长度相同的合法括号匹配序列有:
"()(())", "((()))", "()()()", "(()())",其中LCS( "(())()", "()(())" )为4,其他三个都为5,所以输出3. 
输入描述:
输入包括字符串s(4 ≤ |s| ≤ 50,|s|表示字符串长度),保证s是一个合法的括号匹配序列。


输出描述:
输出一个正整数,满足条件的t的个数。

输入例子1:
(())()

输出例子1:
3
'''



'''
思路:首先利用递归生成与目标序列长度相同的括号匹配序列,然后分别计算目标序列和生成序列的最长公共子序列。
计算方法:先求出目标序列和生成序列长度减1的所有子序列列表,比较两列表是否有公共子序列,若有,则输出子序列的长度,若无,则递归生成
目标序列和生成序列长度减2的所有子序列列表,继续比较,以此类推,直至找到公共子序列
'''

string = input()  # 输入括号匹配序列
length = len(string)  # 计算序列长度


def generate_string(l):  # 利用递归生成与参数长度相同的序列
    if l == 2:
        return ['()']
    else:
        str_l = [i for i in map(lambda x: '()' + x, generate_string(l-2))]
        str_m = [i for i in map(lambda x: '(' + x + ')', generate_string(l-2))]
        str_r = [i for i in map(lambda x: x + '()', generate_string(l-2))]

    str_l.extend(str_m)
    str_l.extend(str_r)
    str_l = list(set(str_l))
    return str_l

g_strings = generate_string(length)  # 根据已知的目标长度生成符合条件的序列列表
g_strings.remove(string)  # 从生成的序列列表中移除目标序列


def get_children(s):  # 得到比参数序列长度小1的子序列
    children = []
    for i in range(len(s)):
        children.append(s[:i] + s[i+1:])
    children = list(set(children))
    return children


def lcs(str_as, str_bs):  # 计算两个参数序列列表中最长公共子序列的长度
    for each_a in str_as:  # 若str_as和str_bs间有公共序列,则返回该序列的长度
        if each_a in str_bs:
            return len(each_a)
    # 若str_as和str_bs间无公共序列
    str_as_children = []
    str_bs_children = []

    for each_a in str_as:  # 计算str_as序列列表中所有序列长度减1的子序列列表
        str_as_children.extend(get_children(each_a))
    for each_b in str_bs:  # 计算str_bs序列列表中所有序列长度减1的子序列列表
        str_bs_children.extend(get_children(each_b))

    str_as_children = list(set(str_as_children))  # 删除重复项
    str_bs_children = list(set(str_bs_children))

    return lcs(str_as_children, str_bs_children)  # 递归计算两个参数序列列表中最长公共子序列的长度

results = []
for each_str in g_strings:  # 计算所有生成序列和目标序列的最长公共子序列的长度
    results.append(lcs([each_str], [string]))

max_lcs = max(results)  # 计算需要题目要求输出的结果
count = 0
for each in results:
    if each == max_lcs:
        count += 1

print(count)


'''
此程序在测试'((())())'时结果不正确
正确的答案是9
此程序得到的答案是8
'''

1个回答

起码要有代码看看,是不是复杂度太高。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐