笔试-最长公共子括号序列

发表于 | 更新于

题目

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的个数。

输入

(())()

输出

3

题解

长度相同的不同的匹配括号序列的LCS最长肯定为N-1,枚举每个左括号，将该左括号移动到其他位置，使得序列仍然匹配，统计即可，注意会有重复，扔到set中去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
  
bool valid(string str){
    stack<int> pos;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){
            pos.push(i);
        }else if(pos.empty()){
            return false;
        }else{
            pos.pop();
        }
    }
    return pos.empty();
}
set<string> ans;
  
int main()
{
    string str;
    cin>>str;
    int maxLen = 0;
    for(int i=0;i<str.size();i++){
        string afterErase(str);
        afterErase.erase(i,1);
        for(int j=0;j<afterErase.size();j++){
            if(j==i) continue;
            string afterInsert(afterErase);
            afterInsert.insert(j,1,str[i]);
            if(valid(afterInsert)&&afterInsert!=str){
                ans.insert(afterInsert);
            }
        }
    }
    cout<<ans.size()<<endl;
    return 0;
}