AcWing 783. 括号序列-java
原题链接
中等
作者:
单箭头
,
2019-05-15 09:21:29
,
所有人可见
,
阅读 1111
java 代码
public class 括号序列 {
private static final int mod=1000000007;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[] str1=sc.nextLine().trim().toCharArray();
char[] str2=sc.nextLine().trim().toCharArray();
int[] cnt1=new int[str1.length+1];
int[] cnt2=new int[str2.length+1];
Valid(cnt1,str1);
Valid(cnt2,str2);
//如果两个合并后不是合法的,那就不用合并了
if(cnt1[str1.length]+cnt2[str2.length]!=0) System.out.println(0);
else {
//dp(i,j):就是第一个序列的前i个括号,与第二个序列的前j个括号,交错组成的合法括号序列个数
int[][] dp=new int[str1.length+1][str2.length+1];
for(int i=0;i<=str1.length;i++){
for (int j=0;j<=str2.length;j++){
//初始化
if(i==0 && j==0) dp[i][j]=1;
else {
if(cnt1[i]+cnt2[j]>=0){
if(i>0) dp[i][j]+=dp[i-1][j];
if (j>0) dp[i][j]+=dp[i][j-1];
dp[i][j]%=mod;
}
}
}
}
System.out.println(dp[str1.length][str2.length]);
}
}
private static void Valid(int[] cnt,char[] chars){
for(int i=0;i<chars.length;i++){
if (chars[i] == '(') {
cnt[i+1]=cnt[i]+1;
}else cnt[i+1]=cnt[i]-1;
}
}
}
/**
* 类型题思路总结:
* 对于括号序列,如果将左括号看做1,右括号看做-1,那么合法序列必然满足:
* ① 从左向右遍历过程中,和cnt>=0;
* ② 遍历结束后,和cnt=0.
* 然后对于合法括号序列,一般都是使用栈来进行处理,左括号入栈,遇到右括号出栈,最后判断栈是否为空
*/
不行,提交到蓝桥杯官网那里ac不了