题目描述

blablabla

样例

class Solution {
    Map<String, List<Integer>> map = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        // 1 涉及括号组合类的一般要使用dfs。这里并不是真实添加括号，每个符号将表达式分为left,right两部分。对应的结果集合组合计算。
        // 2 递归遍历left, right部分，直到表达式为纯数字。 对于 表达式exp，可以使用map缓存结果，递归遍历时可以快速返回结果
        return dfs(expression);
    }

    List<Integer> dfs(String exp) {
        if (map.containsKey(exp)) return map.get(exp);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < exp.length(); i++) {
            char ch = exp.charAt(i);
            if (ch == '+' || ch == '-' || ch == '*') {
                List<Integer> left = dfs(exp.substring(0, i));// 递归遍历左右两部分
                List<Integer> right = dfs(exp.substring(i + 1));
                for (int l : left) {
                    for (int r : right) { // 组合计算
                        if (ch == '+') res.add(l + r);
                        else if (ch == '-') res.add(l - r);
                        else res.add(l * r);
                    }
                }
            }
        }
        if (res.isEmpty()) res.add(Integer.parseInt(exp));
        map.put(exp, res);
        return res;
    }
}