最长公共子括号序列_网易笔试题

一个合法的括号匹配序列被定义为:
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.

def isValid(str): # 判断该字符串是否是合法的括号序列 stack = [] for i in range(len(str)): if str[i] == '(': stack.append(str[i]) else: # 去stack里匹配一个左括号 if len(stack) == 0 or stack[-1] != '(': return False else: stack.pop() return not stack # 得到输入字符串 input_str = input() n = len(input_str) # 思路：取出字符串中的某一个字符c，得到一个剩余字符串remain_str，依次把c插入到remain_str中 # 得到新的字符串，如果该字符串是合法的括号序列，并且与源字符串不相等，则个数加1 # 关键点：对于LCS(s, t)，必然会存在长度为len(s) - 1的公共子序列 count = 0 new_str_list = [] for i in range(n): c = input_str[i] remain_str = input_str[:i] + input_str[i + 1:] # 分别把c插入到remain_str中 for j in range(len(remain_str) + 1): new_str = remain_str[:j] + c + remain_str[j:] # 判断new_str是否是合法的括号序列，并且与源字符串不相等，并且这个new_str也不能重复 if new_str != input_str and isValid(new_str) and new_str not in new_str_list: new_str_list.append(new_str) count += 1 print(count)

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashSet; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String string; while((string = br.readLine()) != null) System.out.println(solve(string)); } // 判断是否为合法的括号序列 private static boolean isValid(String seq) { Stack<Character> stack = new Stack<>(); for(int i = 0; i < seq.length(); i++){ if(seq.charAt(i) == '(') stack.push('('); else{ if(stack.isEmpty()) return false; else stack.pop(); } } return stack.isEmpty(); } private static int solve(String s) { String s1, s2; HashSet<String> set = new HashSet<>(); for(int i = 0; i < s.length(); i++){ s1 = s.substring(0, i) + s.substring(i + 1); for(int j = 0; j < s1.length(); j++){ s2 = s1.substring(0, j) + s.charAt(i) + s1.substring(j); // 如果是合法的括号序列则加入集合 if(isValid(s2)) set.add(s2); } } return set.size() - 1; // 把自己减去 } }

最长公共子括号序列

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题