网易的笔试题，代码已经写好，但一直无法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
'''
