首页 > 试题广场 >

最长公共子括号序列

[编程题]最长公共子括号序列
  • 热度指数:3892 时间限制: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
根据题意,当且仅当修改距离为 1 时 LCS 最大。很容易证明对于两种基本序列 (()) 和 ()() 都有距离为 1 的合法修改。

原本想的是对每个左括号,跟每个右括号替换,判断合法后累计。
后来发现会漏掉一些情况,那就暴力得干脆一点,把每个符号插入到任意位置,判合法,去重,累计。

更新:我后来想了下,上面的叙述有问题。
根据题意,要想使得 LCS 最大,删去任意一个字符即可获得 LCS = |s| - 1 ,再把该字符插到与原来不同的任意位置可以维持原长度,而不影响 LCS 的计算。

因此最暴力的做法是枚举每个字符,把它插入到任意位置,判合法,去重,累计。

优化 1 :插入是插到指定位置的字符之前,如果插入的字符和该位置的字符相同,则插入后还是原字符串,可以跳过这种情况。否则最后的结果要 - 1 。
优化 2 :左右两边一定是左右括号,不用移动它们。但字符却可以插到它们的后面。

判合法:实际上就是括号匹配的平衡性。在这里,如果我们从前到后遍历,左括号可以暂时多于右括号,但不可以少于,因为能够闭合右括号的左括号都在左边了。每次成功闭合一对括号把数量 - 1 ,得到负数说明不平衡。
#include <stdio.h>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

char str[55];

void read() {
    scanf("%s", str);
}

bool test(const string& s) {
    int cnt = 0;
    for (int i = 0; s[i]; ++i) {
        s[i] == '(' ? ++cnt : --cnt;
        if (cnt < 0) {
            return false;
        }
    }
    return true;
}

void work() {
    set<string> record;
    for (int i = 1; str[i+1]; ++i) {
        string tmp(str);
        tmp.erase(i, 1);
        for (int j = 1; str[j]; ++j) {
            if (str[i] == str[j]) continue;
            string s(tmp);
            s.insert(j, 1, str[i]);
            if (test(s)) {
                record.insert(s);
            }
        }
    }
    printf("%lu\n", record.size());
}

int main() {
    read();
    work();
    return 0;
}

编辑于 2017-09-22 18:26:04 回复(15)
package go.jacob.day911;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/*
 * 答案参考@郑耀钧
 * 
 * 我原本的思路是:先找出某个括号字符串的左右合法的全排序字符串
 * 然后用动态规划构造找到最大子串方法LCS,最后做统计
 * 不过很遗憾,这个方法超时了。所以参考了@郑耀钧 的解法,如下
 * 
 * 根据题意,当且仅当修改距离为 1 时 LCS 最大。
 * 很容易证明对于两种基本序列 (()) 和 ()() 都有距离为 1 的合法修改。
 * 原本想的是对每个左括号,跟每个右括号替换,判断合法后累计。
 * 后来发现会漏掉一些情况,那就暴力得干脆一点,把每个符号插入到任意位置,
 * 判合法,去重,累计。
 */
public class Demo2 {
	private static Set<String> set = new HashSet<String>();
	static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		getSequence(str);
		System.out.println(set.size() - 1);
		sc.close();

	}

	private static void getSequence(String str) {
		for (int i = 0; i < str.length(); i++) {
			StringBuilder sb = new StringBuilder(str);
			char c = str.charAt(i);
			sb.deleteCharAt(i);
			for (int j = 0; j < str.length(); j++) {
				sb.insert(j, c);
				if (isLegal(sb.toString())) {
					set.add(sb.toString());
				}
				sb.deleteCharAt(j);
			}
		}
	}

	private static boolean isLegal(String s) {
		int left = s.length() / 2, right = s.length() / 2;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(')
				left--;
			else
				right--;
			if (right < left)
				return false;
		}
		return true;
	}
}


编辑于 2017-09-11 15:03:16 回复(19)

语言:C++ 运行时间: 4 ms 占用内存:376K 状态:答案正确
思路参考@夭寿啦要没Offer啦
使用hash表记录符合的串,即可不用判重。
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

#include <iostream>
#include <string>
#include <map>
using namespace std;
int len;
bool ifLegal(string str);
int main()
{
    string s; cin >> s;
    len = s.size();
    map<string, int> hash;
    for (int i = 0; i < len; i++) {
        string temp = s.substr(0, i) + s.substr(i + 1, len - i - 1);
        for (int j = 0; j < len; j++) {
            string t = temp.substr(0, j) + s[i] + temp.substr(j, len - 1 - j);
            if (t != s && ifLegal(t)) hash[t] = 0;
        }
    }
    cout << hash.size();
    return 0;
}
bool ifLegal(string str)
{
    int n = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == '(') n++;
        else n--;
        if (n < 0) return false;
    }
    return true;
}
发表于 2017-10-10 10:38:24 回复(4)
因为要求的T需要和S不一样,所以T和S的最长公共子括号序列的长度最多为原字符串的长度N减1,而这个N-1可以通过只改变1个字符在S中的位置得到,方法是:遍历S,将每个位置上的字符尝试插入到剩余的字符串的任意位置上(两重循环),如果这个组合后的字符串是个合法的括号序列,那么它和原字符的公共子括号序列长度就是N-1,即最长,最后的结果是set集合大小减1的原因是里面还会包含原字符串

#include <iostream>
#include <set>
using namespace std;

bool isValid(string str) {
    int tmp = 0, len = str.size();
    for (int i = 0; i < len; i++) {
        tmp += (str[i] == '(') ? 1 : -1;
        if (tmp < 0) {
            return false;
        }
    }
    return true;
}

int main() {
    string str;
    cin >> str;
    set<string> S;
    int len = str.size();
    for (int i = 0; i < len; i++) {
        string w = str.substr(0, i) + str.substr(i+1);
        for (int j = 0; j < len - 1; j++) {
            string u = w.substr(0, j) + str[i] + w.substr(j);
            if (isValid(u)) {
                S.insert(u);
            }
        }
    }
    cout << (int)S.size() - 1 << endl;
}

发表于 2017-09-10 17:06:28 回复(1)
#include<iostream>
#include<string>
#include<set>
#include<stack>
using namespace std;
string s;
bool judge(string);
int main(){
    int i,j;
    while(cin>>s){
        set<string> k;
        for(i=0;i<s.length();i++){
            char t=s[i];
            string tmp=s;
            tmp.erase(tmp.begin()+i);
            for(j=0;j<=tmp.length();j++){
                string ti=tmp;
                ti.insert(ti.begin()+j,t);
                k.insert(ti);
            }
        }
        int res=0;
        for(set<string>::iterator it=k.begin();it!=k.end();it++)
            judge(*it)?res++:res=res;
        printf("%d\n",res);
    }
}
bool judge(string x){
    if(x==s) return false;
    stack<char> stk;
    for(int i=0;i<x.length();i++)
        if(x[i]=='(') stk.push(x[i]);
        else{
            if(stk.empty()) return false;
            if(stk.top()!='(') return false;
            stk.pop();
        }
    return stk.empty()==true;
}

发表于 2017-09-18 19:51:08 回复(0)
//StringBuilder对于经常改变字符串来说效率最高
//两次循环,第一次遍历选择不同位置的,第二次将其插入到剩余字符串任意位置
//最后添加到set中去重,最后将原来的一次减去
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class 字符串最大子集数 {
    public static boolean isok(String str) {
        int left=0,right=0;
        for(int i=0;i<str.length();i++) {
            if(str.charAt(i)=='(') left++;
            else right++;
            if(right>left) break;
        }
        if(right!=left) return false;
        return true;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        Set<String> set=new HashSet<>();
        StringBuilder temp;
        StringBuilder temp1;
        for(int i=0;i<str.length();i++) {
            temp=new StringBuilder();
            temp.append(str.substring(0,i)+str.substring(i+1));
            for(int j=0;j<=temp.length();j++) {
                temp1=new StringBuilder();
                temp1.append(temp.substring(0, j)+String.valueOf(str.charAt(i))+temp.substring(j));
                if(isok(temp1.toString())) set.add(temp1.toString());
            }
        }
        System.out.println(set.size()-1);
    }
}

编辑于 2017-09-16 20:41:16 回复(0)
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)
参考LeetCode的 Generate Parentheses的做法把序列都生成出来,然后lcs判断,然后把不对和原序列排除,然而花了快一个小时还是没ac,放弃了.....括号序列可以参考这个博客http://blog.csdn.net/yutianzuijin/article/details/13161721,有人做出来了请好心人回复我一下。
编辑于 2017-09-09 20:17:27 回复(2)
思路:将输入字符全排列,将重复字符唯一话处理(Set可以解决)以及与原始字符相同的字符除去后,分别与原始字符求CLS。
保留最大长度的CLS,并计数即可,AC50%。

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String t = sc.nextLine();
        LinkedList<String> list = permutation(t);
        HashSet<String> set = new HashSet<>();
        int max = 0;
        int count = 0;
        Iterator it = list.iterator();
        while (it.hasNext()) {
            String temStr = it.next().toString();
            if (!isHe(temStr))
                continue;
            if (temStr.equals(t))
                continue;
            set.add(temStr);
        }
        
        Iterator it2 = set.iterator();
        while(it2.hasNext()){
            String temStr2 = it2.next().toString();
            int temS = getMaxSubstringLen(t, temStr2);
            if (temS > max) {
                count = 0;
                max = temS;
                count++;
            } else if (temS == max) {
                count++;
            } else
                continue;
        }
        System.out.println(count);
    }
    // 将字符t全排列
    public static LinkedList<String> permutation(String str) {
        LinkedList<String> linkedString = new LinkedList<String>();
        if (str.length() <= 1) {
            linkedString.add(str);
            return linkedString;
        }
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            // consider the case in which the characters may be duplicated.
            if (i > 0 && ch == str.charAt(i - 1)) {
                continue;
            }
            String newStr = remove(str, i);
            LinkedList<String> newStrList = permutation(newStr);
            for (int j = 0; j < newStrList.size(); j++) {
                linkedString.add(ch + newStrList.get(j));
            }
        }
        return linkedString;
    }
    public static String remove(String str, int i) {
        if (i == 0)
            return str.substring(1, str.length());
        if (i == str.length() - 1)
            return str.substring(0, i);
        return str.substring(0, i) + str.substring(i + 1, str.length());
    }
    // 返回两个字符串的最长公共子序列的长度
    public static int getMaxSubstringLen(String x, String y) {
        int xLen = x.length() + 1;
        int yLen = y.length() + 1;
        int rLen = xLen > yLen ? xLen : yLen;
        int cLen = xLen < yLen ? xLen : yLen;
        int[][] c = new int[rLen][cLen];
        for (int i = 1; i < rLen; i++) {
            for (int j = 1; j < cLen; j++) {
                if (x.charAt(i - 1) == y.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else if (c[i - 1][j] >= c[i][j - 1]) {
                    c[i][j] = c[i - 1][j];
                } else {
                    c[i][j] = c[i][j - 1];
                }
            }
        }
        return c[xLen - 1][yLen - 1];
    }
    public static boolean isHe(String str) {
        Stack<Character> stack = new Stack<>();
        boolean flag = true;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(')
                stack.push(str.charAt(i));
            else {
                if (stack.isEmpty()) {
                    flag = false;
                } else {
                    char c = stack.pop();
                    if (c != '(')
                        flag = false;
                }
            }
        }
        return flag;
    }
}
  
发表于 2017-09-09 22:43:30 回复(0)
先用dfs产生所有合法括号序列,然后通过LCS算法计算字符串s和所有这些合法序列的长度(s本身除外)。AC 50%
importjava.util.Scanner;
importjava.util.ArrayList;
importjava.lang.Math;
importjava.util.List;
publicclassMain{
    publicstaticintnumberofLongest(){
        Scanner in=newScanner(System.in);
        String s=in.nextLine();
        intn=s.length();
        List<String> allmatch=GetAllSeries(n/2);
        intmatchnumber=allmatch.size();
        int[] res=newint[matchnumber];
        intmaxLen=0;
        for(inti=0;i<allmatch.size();i++){
            intmatchlen=LCS(s,allmatch.get(i));
            res[i]=matchlen;
            if(matchlen!=n)
                maxLen=Math.max(maxLen,matchlen);
        }
        intcount=0;
        for(inta:res)
            if(a==maxLen)
                count++;
        returncount;
        }
    publicstaticintLCS(String s1,String s2){
        intm=s1.length();
        intn=s2.length();
        int[][] dp=newint[m+1][n+1];
        for(inti=0;i<=m;i++){
            for(intj=0;j<=n;j++){
                if(i==0||j==0)
                    dp[i][j]=0;
                elseif(s1.charAt(i-1)==s2.charAt(j-1))
                    dp[i][j]=dp[i-1][j-1]+1;
                elsedp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
            }
        }
        returndp[m][n];
    }
    publicstaticList<String> GetAllSeries(intn){
            List<String> res=newArrayList<>();
            String cur="";
            helpGetAllSeries(res,cur,n,n);
            returnres;
        }
     publicstaticvoidhelpGetAllSeries(List<String> res,String s,intleft,intright){
         if(left==0&&right==0){
             res.add(s);
         }
         if(left>0)
             helpGetAllSeries(res, s+"(", left-1, right);
         if(right>left)
             helpGetAllSeries(res, s+")", left, right-1);
     }
     publicstaticvoidmain(String[] args){
        List<String> res=GetAllSeries(3);
        System.out.println(numberofLongest());
    }
     
     
}
发表于 2017-09-10 00:51:37 回复(0)
s = list(input())
def is_valid(s):
    l, r = 0,0
    for i in s:
        if i == "(":
            l+=1
        else:
            r+=1
        if r>l:
            return False
    return True
l = len(s)
res = []
for i in range(l):
    s_1 = s.copy()
    cur_value = s_1.pop(i)
    s_new = s_1.copy()
    for j in range(l):
        if i==j:
            continue
        s_new.insert(j, cur_value)
        if is_valid(s_new) and s_new!=s:
            if s_new not in res:
                res.append(s_new)
        s_new = s_1.copy()    
print(len(res))

发表于 2020-09-11 16:21:48 回复(0)
## 输入转为字符串
s = list(input())
## 保存 t 序列
s_set = []
## 暴力循环
length = len(s)
# 遍历序列中每个值,采用pop删除,接着用insert插入在不同位置
# 当序列合法时保存 
# 合法性判断依据 无论序列多长,序列从左到右,num('(')>=num(')')始终成立
# 初始化计数器count ,当count==lenght,数据合法,进行保存
# 即每次计数中num('(')>=num(')')成立,计数器+1,
# 最后len(t)即可
for i in range(length):
    s_1 = s.copy() #初始化序列
    value = s_1.pop(i) #
    s_new = s_1.copy()
    for j in range(length):
        s_new.insert(j,value)
        ###判断合法性
        num_left = num_right = 0
        count = 0
        for p in range(length):
            num_left = len([x for x in s_new[:p] if x == '('])
            num_right = len([x for x in s_new[:p] if x == ')'])
            if num_left >= num_right:
                count += 1
        if count == length:
            if s_new not in s_set:
                s_set.append(s_new)
        s_new = s_1.copy()

s_result = [s]
for i in s_set:
    if i not in s_result:
        s_result.append(i)
print (len(s_result)-1)

发表于 2018-07-14 20:32:23 回复(0)
a = input()
import copy
list1 = []
a_l   = len(a)
for i in range(len(a)):
    if a[i] == '(':list1.append(0)
    else:list1.append(1)
#判断合法化,注意一旦数列输入到这个函数里面的时候,数列将被改变
def legal(list1):
    i = -1
    tem = 0
    while list1 and i <= len(list1)-2:
        i += 1
        if list1[i] == 0 and list1[i+1] == 1 and len(list1) != 2:
            del list1[i]
            del list1[i]
            i = -1
        elif len(list1) == 2 and (list1[i] != 0 or list1[i+1] != 1) :
            tem = 0
            break
        elif len(list1) == 2 and list1[i] == 0 and list1[i+1] == 1 :
            tem = 1
            break
        else:
            continue
    return tem
#重复性判断函数
list4 = []
def repeat(list3):
    if list3 not in list4:
        return True
    else:
        return False
def main():
    n = 0
    while n == 0:
        for j in range(len(list1)):
            list2 = copy.deepcopy(list1)
            tem = list1[j]
            del list2[j]
            for i in range(len(list2)+1):
                list3 = copy.deepcopy(list2)
                list3.insert(i,tem)
                list5 = copy.deepcopy(list3)
                #print(list4)
                if  list5 != list1 and repeat(list5) and legal(list5) : 
                    n += 1
                    list4.append(list3)
                else: 
                    continue
            list2.insert(j,tem)
    print(n)
    
main()

发表于 2018-05-21 21:47:43 回复(0)
整体思路是:求取和s拥有公共最长子序列的t的个数,那么最长子序列元素个数就是len(s)-1,
所以就通过将s的元素(除首尾外,因为合法元素首尾肯定是左右括号)逐个pop出来再在各个位置insert回去,
得到一系列的t(这些t只要合法,那肯定就和s有最长公共子序列,长度为(len(s)-1))后;
判断这些t是否合法,再输出合法t的数量即可
读取括号序列后:
1.经过一系列pop和insert操作生成s3(元素换位后生成的所有t的列表)
2.去除重复的t及原始s0后得到s4
3.判断s4中t的合法性并计算s4中合法t的个数
#最长公共字括号序列最终版

#1.经过一系列pop和insert操作生成s3(元素换位后生成的所有t的列表)

s0 = list(input())    
l = len(s0)           
#print(l)
k1 = 0
s3 = []
#s0 原始括号序列
#s1 原始括号序列的备份:会被pop掉一个元素
#s2 备份被pop掉一个元素的s1后再在自身的各个位置insert一个元素
#s3 包含所有得到的t
#s4 筛选出不重复的且与原始s0不同的t
for i in range(l):    #遍历s0中各元素,把每个元素都拿出来并插入新位置(这里是所有位置都插了,
                      #因为后面反正会判断重复性),
    s1 = s0.copy()    #s0的备份:s1的初始化,因为每次拿数据都是从最初的s0上拿,所以拿数据之前的s0要保留
    #print(s1)
    a = s1.pop(i)     #pop数据
    s2 = s1.copy()    #s1的备份:拿了数据以后要在各个位置插入,所有pop后的s1要保留
    #print(a)
    for j in range(l):#按照原来s0 的位置信息在各个位置插入刚刚pop出来的a
        s2.insert(j,a)
        #print(s1)
        s3.append(s2) #生成新的t并加入到元素为t的s3中
        s2 = s1.copy()#初始化s2
        j += 1
        
#2.去除重复的t及原始s0后得到s4

s4 = []               
for i in s3:
    if not i in s4:  #if not (i in s4 or i == s0):   也可以用并集的互补集表示
        if i != s0 : # and i[0] == '(' and i[len(s0)-1] != '('这里判不判断首位是不是‘(’并不重要,
       #毕竟后面也有判断按顺序读取s4【m】元素时,左括号数量是否大于右括号数量,一旦第一个是右括号,
       #元素s4【m】就不合法了
            s4.append(i)
#print(s3,len(s3))
#print(s4,len(s4))

#3.判断s4中t的合法性并计算s4中合法t的个数

for m in range(len(s4)):   #遍历s4中的各个t
    n0 = 0                 #参数初始化
    n1 = 0
    for n in range(len(s4[m])): #遍历单个t的各个元素时,判断左括号是否多于右括号,一旦左括号少于右括号,
        if s4[m][n] == '(':     #就是不合格括号序列, k1(作为flag参数)减一,
            n0 += 1
        else:
            n1 += 1
        if n0 < n1 :
            k1 -= 1
            break
    k1 += 1                     #给s4中的每个t都加1,在遇到不合法序列时减一,
print(k1)                       #其实这个加1可以省略,直接拿len(s4)来减就好了


编辑于 2018-03-28 11:10:32 回复(0)
import java.util.*;

public class KindsSubSeq {
    /*
     * 参考解题思路:https://www.nowcoder.com/test/question/done?tid=14539495&qid=126953#summary
     * 最长的子序列和原字符串只相差一,暴力替换原字符串任意个字符,然后判断新生成的字符是否是满足括号特性,满足则添加到set集合中(自动去重)
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            set.clear();
            String line = scanner.nextLine();
            getSequence(line);
//            包含原字符串
            System.out.println(set.size() - 1);
        }
    }

    private static void getSequence(String line) {
        for (int i = 0; i < line.length(); i++) {
//            每次删除一个字符
            StringBuilder stringBuilder = new StringBuilder(line);
            char c = line.charAt(i);
            stringBuilder.deleteCharAt(i);
            for (int j = 0; j < line.length(); j++) {
//                对应位置插入一个字符
                stringBuilder.insert(j, c);
                if (isValidBracket(stringBuilder.toString())) {
                    set.add(stringBuilder.toString());
                }
//                下次循环判断,删除该字符
                stringBuilder.deleteCharAt(j);
            }
        }
    }

    //    判断某字符串是否满足括号特性
    private static boolean isValidBracket(String str) {
        int left = str.length() / 2;
        int right = left;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                left--;
            } else {
                right--;
            }
            if (left > right) {
                return false;
            }
        }
        return true;
    }

    private static Set<String> set = new HashSet<>();
}
发表于 2018-03-27 08:54:54 回复(0)

import java.util.*;

public class Main {

    private static HashSet<String> set = new HashSet<String>();

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

/*

 * 思路:只挪动一个符号,得到的合法序列就是满足自子序列最大的序列。子序列的长度=|s|-1

 * 所以,对每一个半括号,随意插入任意位置,判断是否合法,合法则放到set里

 * 最后的数字=size()-1(排除原来的序列)

 * */

        //小优化:原本的序列是合法序列,则头和尾的符号是确定的,没有必要移动。

        for(int i=1;i<s.length()-1;i++){

            StringBuilder bd = new StringBuilder(s);

            char c = bd.charAt(i);

            bd.deleteCharAt(i);

            for(int j=1;j<s.length()-1;j++){

                bd.insert(j,c);

                if(isLeagal(bd)){

                    set.add(bd.toString());

                }

                bd.deleteCharAt(j);

            }


        }

        //有一个是原序列

        System.out.println(set.size()-1);

        sc.close();

    }

    

    private static boolean isLeagal(StringBuilder bd){

        int count =0;

        for(int i=0;i<bd.length();i++){

            if(bd.charAt(i) == '('){

                count++;

            }else{

                count--;

            }

            if(count<0)return false;

        }

        return true;

    }


}


发表于 2018-03-25 16:47:09 回复(0)
/*参考一楼二楼内容*/
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
    private static Set<String> set = new HashSet<String>();//用来存储 合法 T
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        getT(str);
        System.out.println(set.size() - 1);//去除一条与S重复的数据
        scanner.close();
    }
    //用来查找合法的t
    //遍历字符串,取出一个字符,遍历剩下的字符插入,判断是否合法
    //LCS(S,T)的最大值就是|S|-1
    //方法原理:根据最长公共子序列去反向推T
    private static void getT(String str) {
        for (int i = 0; i < str.length(); i++) {
            StringBuffer sb = new StringBuffer(str);
            char ch = sb.charAt(i);//每次取出的字符
            sb.deleteCharAt(i);//删除sb中取出的字符
            for (int j = 0; j < str.length(); j++) {
                sb.insert(j, ch);//将字符遍历插入
                if (isLegal(sb.toString())) {
                    set.add(sb.toString());
                }
                sb.deleteCharAt(j);//将之前插入的字符删除掉
            }
        }
    }
    //用来判断是否合法
    //判断标准:当left多,且第一个不为)时,合法
    private static boolean isLegal(String str) {
        int left = 0,right = 0;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            //left和rigth谁小,就证明哪边的括号多
            if (ch == '(') left--;
            else right--;
            if (left > right) return false;
        }
        return true;
    }
}
 
发表于 2018-03-25 14:05:55 回复(0)

python3

# coding=utf-8
__author__ = 'xiaofu'

def solution(s):
    # 只需要移动一个字符即可,保持其他n - 1个的相对位置不变
    # 然后判断这样生成的新字符串是否是合法的括号序列

    # 快速去重
    target_s = set()

    for i, c in enumerate(s):

        # 删除第i个位置的字符
        s1 = s[0: i] + s[i + 1: ]

        # len(s) = len(s1) + 1
        # 假设s1为 xyz 用下划线表示可以插入的位置 _x_y_z_
        for j in range(len(s1) + 1):
            # 将字符c插入到任意一个位置
            # [0:0]会生成空串
            s2 = s1[0: j] + c + s1[j:]

            # 直接由后面使用set来判断是否加入了与s相同的序列
            # 效率会更高,不用每次都检查一遍字符串
            # if s2 == s:
            #     # 有可能会产生和s一样的结果
            #     continue

            # 检查括号是否匹配
            left_parentheses = 0    # 左括号数量
            # 不需要再多一个右括号的变量,否则判断更加麻烦
            # right_parentheses = 0   # 右括号数量
            for char_in_s2 in s2:
                if char_in_s2 == '(':
                    left_parentheses += 1
                else:
                    left_parentheses -= 1

                if left_parentheses < 0:
                    # 说明出现了左边没多余(,而出现了),导致这个)不可能闭合
                    break

            if left_parentheses == 0:
                # s2 is valid
                target_s.add(s2)

    if s in target_s:
        return len(target_s) - 1

    return len(target_s)

# def insert_string_before(source, string, position):
#     return source[0: position] + string + source[position:]

def main():
    s = input().strip()
    print(solution(s))
    # print(solution("((())())"))

if __name__ == '__main__':
    main()
发表于 2017-10-18 19:57:12 回复(1)

先正向遍历一遍,然后反向遍历一遍,再正向遍历两遍,时间复杂度为O(n)

#include<stdio.h>
#include<stdlib.h>
int main(void){
    int left_kuohao = 1;
    int right_kuohao = 0;
    char before = '(';
    char s[51];
    int sum = 0;
    scanf_s("%s", s,30);
    int i;
    int alter_left_kuohao = 0;
    for (i = 1; s[i]; i++){
        if (s[i] == '('){
            left_kuohao++;
            alter_left_kuohao++;
            if (before == ')'){
                sum += right_kuohao;
            }
        }
        else{  right_kuohao++;
            if (before == '('){
                sum += alter_left_kuohao;
            }
            if (left_kuohao - right_kuohao == 0){
                alter_left_kuohao = -1;
            }
        }
        before = s[i];
    }
    int lenth = i;
    left_kuohao = 0;
    right_kuohao = 1;
    char after = ')';
    int alter_right_kuohao = 0;
    for (i = i - 2; i > -1; i--){
        if (s[i] == ')'){
            right_kuohao++;
            alter_right_kuohao++;
            if (after == '('){
                sum += left_kuohao;
            }
        }
        else{
            left_kuohao++;
            if (after == ')'){
                sum += alter_right_kuohao;
            }
            if (right_kuohao == left_kuohao){
                alter_right_kuohao = -1;
            }
        }
        after = s[i];
    }
    int count = 0;
    for (i = 1; i < lenth - 2; i++){
        if (s[i] == ')'&&s[i + 1] == '('){
            count++;
            i++;
        }
        else if (count){
            sum -= count*(count + 1) / 2;
            count = 0;
        }
    }
    if (count >0){
        sum -= count*(count + 1) / 2;
    }
    count = 0;
    left_kuohao = 1;
    right_kuohao = 0;
    for (i = 1; i < lenth - 2; i++){
        if (s[i] == '('&& s[i + 1] == ')'&& left_kuohao > right_kuohao){
            left_kuohao++;
            right_kuohao++;
            count++;
            i++;
        }
        else{
            sum -= count*(count + 1) / 2;
            count = 0;
            if (s[i] == '('){
                left_kuohao++;
            }
            else{
                right_kuohao++;
            }
        }
    }
    if (count >0){
        sum -= count*(count + 1) / 2;
    }
    printf("%d", sum);
    system("pause");
    return 0;
}
编辑于 2017-09-17 21:53:31 回复(0)
做了好久,终于通过了,贴出来记录下
#include<iostream>
#include<set>
#include<string>
using namespace std;
bool fun(string s);
int main()
{
	string s;
	cin >> s;
	set<string> slist;
	for (auto i = 0; i < s.size(); ++i)
	{
		string str = s;
		char ch = str[i];
		str.erase(i, 1);
		for (auto j = 0; j < str.size(); ++j)
		{
			string tem = str;
			tem.insert(j, 1, ch);
			if (fun(tem)&&tem!=s)
				slist.emplace(tem);
		}
	}
	cout << slist.size() << endl;
}

bool fun(string s)
{
	string::iterator beg, end;
	beg = end = s.begin();
	
	while (1)
	{
		while (beg != s.end() && *beg != '(')
			++beg;
		while (end != s.end() && *end != ')')
			++end;
		if (beg<=end&&beg != s.end() && end != s.end())
		{
			++beg;
			++end;
			continue;
		}
		else if (beg == s.end() && end == s.end())
			return true;
		else
			return false;
	}
}

发表于 2017-09-16 00:17:31 回复(0)