Question description:

Screenshot 2016-10-03 23.28.38.png

My code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> result = new ArrayList<>();
        Map<String, List<Integer>> calculated = new HashMap<>();
        result = compute(calculated, input);
        return result;
    }
    
    public static List<Integer> compute(Map<String, List<Integer>> calculated, String input) {
        List<Integer> ret = new ArrayList<>();
        if (!input.contains("+") && !input.contains("-") && !input.contains("*")) {
            ret.add(Integer.parseInt(input));
            calculated.put(input, ret);
            return ret;
        }
        if (calculated.containsKey(input)) {
            ret = calculated.get(input);
            return ret;
        }
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                String sub1 = input.substring(0, i);
                String sub2 = input.substring(i + 1, input.length());
                List<Integer> list1 = compute(calculated, sub1);
                List<Integer> list2 = compute(calculated, sub2);
                switch(c) {
                    case '+':
                        for (Integer m: list1
                             ) {
                            for (Integer n: list2
                                 ) {
                                ret.add(m + n);
                            }
                        }
                        break;
                    case '-':
                        for (Integer m: list1
                                ) {
                            for (Integer n: list2
                                    ) {
                                ret.add(m - n);
                            }
                        }
                        break;
                    case '*':
                        for (Integer m: list1
                                ) {
                            for (Integer n: list2
                                    ) {
                                ret.add(m * n);
                            }
                        }
                        break;
                }
            }
        }
        calculated.put(input, ret);
        return ret;
    }
}

LeetCode result:

Screen Shot 2016-10-06 at 21.27.00.png

Solution:

Use dynamic programming (DP). For an input string, look for each opertion symbol. For each operation symbol, split the input string into two part: one is to the left of that symbol and the other is to the right. For each sub string, do the same thing as the input string. Use a List<Integer> to record all possible values of each string fomula. Use a Map(<String fomula, List<Integer>) to store all strings that have been calculated to avoid repeated calculation.