1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
                List<Integer> leftExp = diffWaysToCompute(expression.substring(0, i));
                List<Integer> rightExp = diffWaysToCompute(expression.substring(i + 1));
                for (Integer leftEle : leftExp) {
                    for (Integer rightEle : rightExp) {
                        ans.add(compute(leftEle, rightEle, expression.charAt(i)));
                    }
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(Integer.parseInt(expression));
        }
        return ans;
    }

    private int compute(int i, int j, char operand) {
        int ans = 0;
        switch (operand) {
            case '+':
                ans = i + j;
                break;
            case '-':
                ans = i - j;
                break;
            case '*':
                ans = i * j;
                break;
        }
        return ans;
    }
}

在每个sign处把expression一分为二. 递归就行了.

时间复杂度和空间复杂度非常不知道.