题解 | #最长公共子括号序列#

//这个题目一开始想插了，想去先求题目给的那个字符串用递归求出所有的合法的匹配字符，再把每个匹配字符用动态规划去求最长子字符串得出结果。
//加上看了第一个大哥也是这么想的，一条路走到黑，后来发现时间不符号要求，有一半例子超时，再看一看他的复杂度（基本算是2的n次幂）括号多一点就吃不消了
//然后自己想想能不能从别的地方入手，就发现我可以先处理最长子字符串（用动态规划那个）
//通过观察发现，因为不能和原字符串相同，所以最长子字符串基本就是原字符串的长度n减去1，（这里我没细想，基本没跑，也可能跑）
//那既然最长确定是n-1,那我原字符串删去一个字符号就肯定可以和对应字符串删去一个字符相等，所以符合最长子字符串的对应字符串 一定是原字符串拿掉一个字符a，然后在这个字符串任意地方插入这个字符a（换一个字符相当于直接不符合括号合法性了）
//通过循环（n的平方复杂度）得出了所有符合最长子字符串为n-1的结果，然后拿这些结果去判断一下他的括号合法性（这里要用到栈），不相同再用Map字典筛选一下，就得出了最后的结果
//复杂度从2的n次降到了n的平方，我的感想是遇到这种可能同时用到递归和动态规划的题，想想有没有可能是陷阱，一般题目不会猛堆工作量。一定要试一试多分析分析题目看看有没有别的路（感觉我也是狗屎想出来的，平常我肯定一条道走到黑了，所以总结一下）
package main

import (
	"bufio"
	"fmt"
	"os"
)

var M map[string]bool
var lendata1 int
//普通的栈
type Stake1 struct{
	index int
	list []int
	capp int

}
func (thisS *Stake1)newstake(c int){
	thisS.capp = c
	thisS.list = make([]int,thisS.capp)
	thisS.index = -1
}
func (thisS *Stake1)push(num int){
	thisS.index = thisS.index + 1
	thisS.list[thisS.index] = num
}
func (thisS *Stake1)pop()(a int){
	a = thisS.list[thisS.index]
	thisS.index--
	return
}
//判断是否合法
func hefa(s string)bool  {
	st := Stake1{}
	st.newstake(lendata1)
	for i:=range s{
		if s[i]==40{
			st.push(40)
		}else {
			if st.index==-1{
				return false
			}
			st.pop()
		}
	}
	return true

}
func main(){
	in:=bufio.NewScanner(os.Stdin)
	in.Scan()
	data1:=in.Text()
	M=make(map[string]bool)
	lendata1 =len(data1)
	M[data1] = true
	str :=""
	max:=0
        //找到两个字符串（一个是题目给的字符串）都删减一次就能相同的对应字符串（满足n-1的公共子括号）
	for i,_:=range data1{
		kuohao := string(data1[i])
		str = data1[:i]+data1[i+1:]
		str1:=""
		for j:=0;j<lendata1;j++{
			if j!=lendata1-1{
				str1 = str[:j]+ kuohao+str[j:]
			}else {
				str1 = str[:j]+ kuohao
			}
			ok,_ := M[str1]
			if !ok{
				if hefa(str1){
					max= max+1
					M[str1] = true
				}
			}
		}
	}
	fmt.Println(max)

}