首页 > 试题广场 >

最长公共子括号序列

[编程题]最长公共子括号序列
  • 热度指数:96 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 98M,其他语言196M
  • 算法知识视频讲解
一个合法的括号匹配序列被定义为:
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

输入

(())()

输出

3
#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    set<string> S;
    int len = s.size();
    for(int i = 0; i < len; i++) {
        string w = s.substr(0, i) + s.substr(i + 1);
        for(int j = 0; j < len - 1; j++) {
            string u = w.substr(0, j) + s[i] + w.substr(j);
            int tmp = 0;
            for(int k = 0; k < len; k++) {
                tmp += (u[k] == '(' ? 1 : -1);
                if(tmp < 0) {
                    break;
                }
            }
            if(tmp >= 0) {
                S.insert(u);
            }
        }
    }
    cout << (int)S.size() - 1 << endl;
    return 0;
}


发表于 2020-06-23 10:30:35 回复(0)
s = input().strip()
S = set()

len_s = len(s)
for i in range(len_s):
    w = s[:i] + s[i+1:]
    for j in range(len_s - 1):
        u = w[:j] + s[i] + w[j:]
        tmp = 0
        for k in range(len_s):
            tmp += 1 if u[k] == '(' else -1
            if tmp < 0:
                break
        if tmp >= 0:
            S.add(u)

print(len(S) - 1)

发表于 2023-09-23 13:18:28 回复(0)