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

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

暴力

本来用“DFS+剪枝”生成所有合法的括号序列，然后计算这些序列（除原始序列外）与给定括号串的LCA长度。

但是这种做***超时，于是换了一种暴力的方式：把给定括号串的每个字符尝试插在不同的位置，保留下除给定括号串之外的所有合法括号序列，再与给定的括号串计算LCS的长度。

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeMap;

public class Main {
    private static HashSet<String> res;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String parenthesis;
        while((parenthesis = br.readLine()) != null){
            int n = parenthesis.length() >> 1;
            res = new HashSet<>();
            generateParenthesis(parenthesis);
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for(String seq: res){
                if(!seq.equals(parenthesis)){
                    int maxLen = lcs(parenthesis, seq);
                    map.put(maxLen, map.getOrDefault(maxLen, 0) + 1);
                }
            }
            System.out.println(map.lastEntry().getValue());
        }
    }

    private static int lcs(String s1, String s2) {
        int n = s1.length();
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][n];
    }

    private static void generateParenthesis(String str) {
        int n = str.length();
        for(int i = 0; i < n; i++){
            String c = str.substring(i, i + 1);
            String parenthesis = str.substring(0, i) + str.substring(i + 1);
            for(int j = 0; j < parenthesis.length(); j++){
                String s = parenthesis.substring(0, j) + c + parenthesis.substring(j);
                if(!s.equals(str) && isValid(s)){
                    res.add(s);
                }
            }
        }
    }

    private static boolean isValid(String str) {
        int n = str.length();
        int left = 0;
        for(int i = 0; i < n; i++){
            if(str.charAt(i) == '('){
                left++;
            }else{
                if(left > 0){
                    left--;
                }else{
                    return false;
                }
            }
        }
        return left == 0;
    }
}

最长公共子括号序列

输入描述:

输出描述:

输入

输出

暴力

问题信息

热门推荐

通过挑战的用户

相关试题