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.
 * 然后对于合法括号序列，一般都是使用栈来进行处理，左括号入栈，遇到右括号出栈，最后判断栈是否为空
 */