最长公共子括号序列(牛客网网易2018校招题思维+暴力)

古城微笑少年丶 2022-05-13 04:22 165阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/504ad6420b314e5bb614e1684ad46d4d][https_www.nowcoder.com_questionTerminal_504ad6420b314e5bb614e1684ad46d4d]  
来源：牛客网  
  
一个合法的括号匹配序列被定义为:  
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

## 输入 ##

(())()

## 输出 ##

题解:

这题我没写出来。。刚刚才补完，写卷子的时候还以为这题会是个dp+栈判断合法什么的，一看题解傻眼了，居然是暴力。。我居然没写出暴力。感觉这题还是有难度的，要写出这题需要知道一个关键点，就是题目所说的一个字符串子串的LSC一定是串长-1

可以这么想：

将串中的一个元素拿出，那么该串和原串的LCS一定是最大的:原串长-1，然后再将该元素插入到与原来的位置不同的地方，这并不影响LCS大小，也维持了原串的长度。然后枚举所有字串，再判断其合法性就行了。

判断合法性:

从前往后扫一遍字串，无论在那个位置，累计的左括号的数目一定要大于等于右括号的数目  
代码:

#include<stdio.h>
    #include<set>
    #include<algorithm>
    #include<string.h>
    #include<string>
    #include<iostream>
    using namespace std;
    int check(string s)
    {
        int n1=0,n2=0;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='(')
                n1++;
            else
                n2++;
            if(n1<n2)
                return 0;
        }
        return 1;
    }
    int main()
    {
        string s;
        set<string>jud;
        cin>>s;
        for(int i=0;i<s.length();i++)
        {
            string ss=s;
            ss.erase(i,1);
            for(int j=0;j<s.length()-1;j++)
            {
                string ls=ss;
                ls.insert(j,1,s[i]);
                if(check(ls))
                    jud.insert(ls);
            }
        }
        printf("%lld\n",jud.size()-1);
        return 0;
    }

[https_www.nowcoder.com_questionTerminal_504ad6420b314e5bb614e1684ad46d4d]: https://www.nowcoder.com/questionTerminal/504ad6420b314e5bb614e1684ad46d4d