首页 > 试题广场 >

最长公共子括号序列

[编程题]最长公共子括号序列
  • 热度指数:135 时间限制: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
这个题,有一个很重要的隐含条件没有告诉大家,就是任何一个合法字符串(假设长度为 2L    L>=2 ),与另外一个相同长度的合法字符串的  最长公共子括号序列 的长度为  2L-1
所以,这个题从暴力枚举出当前字符串,只改动一个字符的情况,计算出每种可能是否匹配即可,代码如下。

#include <bits/stdc++.h>
using namespace std;

// 计算当前括号是否匹配
bool isValid(string a){
    stack<char> sta;
    for(auto& it:a){
        if(it == '(') sta.push(it);
        else {
            if(sta.size() == 0) return false;
            sta.pop();
        }
    }
    if(sta.size() == 0) return true;
    return false;
}

int getLCS(string a){
    int num = 0;
    // 所有可能的字符串先放到一个 哈希表中,方便去重
    unordered_set<string> hash;
    for(int i=0; i<a.size(); i++){
        // 取出当前位,把剩下的字符串拼接到一起
        char tem = a[i];
        string str = a.substr(0, i) + a.substr(i+1);
        // 把当前位分别插入到后面的字符中
        for(int j=0; j<str.size(); j++)
            hash.insert(str.substr(0, j) + tem + str.substr(j));
    }
    // 去除当前字符串,并计算当前哈希表中合法的字符串的个数
    // 即为结果
    hash.erase(a);
    for(auto& it:hash)
        if(isValid(it)) num++;
    return num;
}

int main() {
    string str;
    cin >> str;
    int res = getLCS(str);
    cout << res << endl;

    return 0;
}


发表于 2019-07-28 08:09:16 回复(2)