括号匹配等一系列问题

问题描述

左括号右边能找到唯一对应的右括号，右括号左边能找到唯一对应的左括号，则该字符串为完整字符串。

现有两列只包含括号的字符串，问多少种差错方式生成完整字符串。

问题分析

第一步，分析两字符串能否合成完整的字符串（即没有多余的左括号或者右括号，否则输出0）。

两字符串交错后，设置一个值n=0，从左往右数，每碰到左括号n++，碰到右括号n--。若n值始终为非负数，则该字符串为完整字符串。

现在观察第一个字符串，设字符串长度为3，如下图所示，有4个可插入空间。类似的n个字符有n+1个插入点。

1552301562784.png

现在统计每个插入点可以插入右括号的个数。例如字符串"(()"，可得插入数列[0,1,2,1]，设为a。

再统计第二个字符串，从起始位置到插入点，碰到左括号-1，碰到右括号+1。例如字符串"())",等数列[-1,0,1]，设为b。

经过几次操作之后，m第一个字符串的可插入点位置，n表示当前正准备插入第二个字符串的字符的位置。表示当前到之后的所有操作的次数。则等于第二个字符串第n位插入第m位，插入第m+1位，插入第m+2位，直至最后的结果，第n位已经插入，计算到n+1位。再考虑到插入时要考虑a[m]>=b[n]的问题。可以得迭代方程

    private int getNums(int[] a, int apoint, int[] b, int bpoint) {
        int result = 0;
        for (int i = apoint; i < a.length; i++) {
            if (a[i]>=b[bpoint]) {                
                result = getNums(a, i, b, bpoint+1);
            }
        }
        return result;
    } 
    

可以通过getNums(a, 0, b, 0)来计算结果。

考虑到迭代有大量重复计算问题，上面的式子可以改成动态规划形式。

    static int[][] dp;

    static private int getNums(int[] arr, int apoint, int[] b, int bpoint) {
        int result = 0;
        if (arr.length-1==apoint) {
            return 1;
        }
        if (b.length-1==bpoint) {
            for (int i = apoint; i < arr.length; i++) {
                if (arr[i]>=b[bpoint]) result++;
            }
            return result;
        }

        for (int i = apoint; i < arr.length; i++) {
            if (arr[i]>=b[bpoint]) {
                if (dp[i][bpoint+1]==0) {
                    dp[i][bpoint+1] = getNums(arr, i, b, bpoint+1);
                }else {
                    System.out.println(i+"==================="+(bpoint+1));
                }
                result += dp[i][bpoint+1];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        int[] aint = new int[a.length()+1];
        int[] bint = new int[b.length()+1];

        for (int i = 0; i < a.length(); i++) {
            if(a.charAt(i)=='('){
                aint[i+1] = aint[i]+1;

            }else {
                aint[i+1] = aint[i]-1;
            }
        }
        for (int i = 0; i < b.length(); i++) {
            if (b.charAt(i)==')') {
                bint[i+1] = bint[i] + 1;
            } else {
                bint[i+1] = bint[i] - 1;
            }
        }

        if (aint[aint.length-1]!=bint[bint.length-1]) {
            System.out.println(0);
            return;
        }

        dp = new int[aint.length][bint.length];

        System.out.println(getNums(aint, 0, bint, 1));

    }

同类问题

现有另一个类似的问题。

题目描述：小Q非常富有，拥有非常多的硬币，小Q的拥有的硬币是有规律的，对于所有的非负整数K,小Q恰好> 各有两个数值为2^k，的硬币，所以小Q拥有的硬币是1，1，2，2，4，4……，小Q卖东西需要支付元钱，请问小Q想知道有多少种组合方案。
输入：一个n (1<=n<=10^18),代表要付的钱
输出：表示小Q可以拼凑的方案数目

输入样例：6
输出样例：3
即：4+2，4+1+1，2+2+1+1

解题思路类似，具体请看后面更新。