首页 > 试题广场 >

最长公共子括号序列

[编程题]最长公共子括号序列
  • 热度指数：3904 时间限制：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
算法知识视频讲解
添加回答
JavaScript
doramc头像 doramc
emmm JS版本。 最长公共子串总是N-1的长度。 穷举所有合法的N-1的子串个数。 
var readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    var arr = line, alen = arr.length, res = new Set();
    for (var i = alen - 2; i > 0; i--) {
        var med = arr.split('');
        var tmp = arr[i];
        med.splice(i, 1);
        for (var j = alen - 2; j >= 0; j--) {
            med.splice(j, 0, tmp);
            if (valid(med.join('')))
                res.add(med.join(''));
            med.splice(j, 1);
        }
    }
    if(res.has(arr))
        res.delete(arr);
    console.log(res.size);
});

function valid(str) {
    var res = [], len = str.length;
    for (var i = 0; i < len; i++) {
        if (str.charAt(i) == '(') {
            res.push('(');
        } else {
            res.pop();
        }
    }
    if (res.length === 0)
        return true;
    else
        return false;
}

发表于 2017-09-11 11:53:37 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 字符串 前端工程师 算法工程师 栈 测试工程师 PHP工程师 哈希 贪心 穷举 网易 2018 Java工程师
来自：网易2018校园招聘编...
上传者：小小
难度：
1条回答 17366浏览

热门推荐

通过挑战的用户

相关试题

最长公共子括号序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号