最长公共子括号序列

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;
	}
}

语言：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;
}

#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;
}

//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);
    }
}

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;
}

#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;
}

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))

## 输入转为字符串
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)

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()

#最长公共字括号序列最终版

#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）来减就好了

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<>();
}

	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;



	    }



	





	}

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()

先正向遍历一遍，然后反向遍历一遍，再正向遍历两遍，时间复杂度为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;
}

#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;
	}
}