代码1

Runtime: 3 ms, faster than 25.41% of Java online submissions for Different Ways to Add Parentheses.

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList();
        List<String> ops = new ArrayList();
        for (int i = 0; i < input.length(); i++) {
            int j = i;
            while (j < input.length() && Character.isDigit(input.charAt(j))) {
                j++;
            }
            ops.add(input.substring(i, j));
            if (j != input.length()) ops.add(input.substring(j, j + 1));
            i = j;
        }
        result = compute(ops, 0, ops.size() - 1);
        return result;
    }
    public List<Integer> compute(List<String> ops, int low, int high) {
        List<Integer> result = new ArrayList();
        if (low == high) {
            result.add(Integer.valueOf(ops.get(low)));
            return result;
        }
        for (int i = low + 1; i <= high - 1; i += 2) {
            String operator = ops.get(i);
            List<Integer> left = compute(ops, low, i - 1);
            List<Integer> right = compute(ops, i + 1, high);
            for(int leftNum:left) {
                for(int rightNum: right){
                    if(operator.equals("+")) result.add(leftNum+rightNum);
                    else if(operator.equals("-")) result.add(leftNum-rightNum);
                    else result.add(leftNum*rightNum);
                }
            }
        }
        return result;
    }
}

代码2

Runtime: 4 ms, faster than 20.57% of Java online submissions for Different Ways to Add Parentheses.

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList();
        List<String> ops = new ArrayList();
        for (int i = 0; i < input.length(); i++) {
            int j = i;
            while (j < input.length() && Character.isDigit(input.charAt(j))) {
                j++;
            }
            ops.add(input.substring(i, j));
            if (j != input.length()) ops.add(input.substring(j, j + 1));
            i = j;
        }
        int n = (ops.size() + 1) / 2;
        ArrayList<Integer>[][] dp=(ArrayList<Integer>[][]) new ArrayList[n][n];
        for (int d = 0; d < n; d++) {
            if (d == 0) {
                for (int i = 0; i < n; i++) {
                    dp[i][i] = new ArrayList();
                    dp[i][i].add(Integer.valueOf(ops.get(i * 2)));
                }
                continue;
            }
            for (int i = 0; i + d < n; i++) {
                dp[i][i + d] = new ArrayList();
                for (int j = i; j < i + d; j++) {
                    ArrayList<Integer> left = dp[i][j];
                    ArrayList<Integer> right = dp[j + 1][i + d];
                    String operator=ops.get(j*2+1);
                    for(int leftNum:left) {
                        for(int rightNum:right){
                            if(operator.equals("+"))
                                dp[i][i+d].add(leftNum+rightNum);
                            else if(operator.equals("-"))
                                dp[i][i+d].add(leftNum-rightNum);
                            else
                                dp[i][i+d].add(leftNum*rightNum);
                        }
                    }
                }
            }
        }
        return dp[0][n - 1];
    } 
}