LeetCode 241. 为运算表达式设计优先级(分治/记忆化递归/动态规划)

---

0 题目

• 241. 为运算表达式设计优先级

1 解题思路

1.1 分治 + 记忆化递归

将字符串按照运算符拆分成左右两个子字符串，分别计算出左右两个子字符串的结果集，再按照拆分运算符对结果集进行合并，对于子字符串也可以通过不断拆分来获得结果集（递归）

以 2 * 3 - 4 * 5 为例，可拆分为：

• 2 和 3 - 4 * 5 两部分，中间是 * 号相连
• 2 * 3 和 4 * 5 两部分，中间是 - 号相连
• 2 * 3 - 4 和 5 两部分，中间是 * 号相连

为了防止重复计算，可以使用Map来保存子字符串对应的结果集。

1.1.1 代码实现

class Solution {
    
    // 记忆化递归
    Map<String, List<Integer>> mem = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
    
        if (expression.length() == 0) {
    
            return new ArrayList<>();
        }
        // 当前表达式已经有解了，直接返回
        if (mem.containsKey(expression)) {
    
            return mem.get(expression);
        }
        // 保存当前表达式的结果
        List<Integer> res = new ArrayList<>();

        int num = 0;
        int index = 0;
        // 考虑表达式仅仅只有一个数字的情况
        while (index < expression.length() && !isOperation(expression.charAt(index))) {
    
            num = num * 10 + (expression.charAt(index) - '0');
            index++;
        }
        if (index == expression.length()) {
    
            res.add(num);
            mem.put(expression, res);
            return res;
        }

        // 继续分割当前表达式 按照运算符
        for (int i = 0; i < expression.length(); i++) {
    
            if (isOperation(expression.charAt(i))) {
    
                List<Integer> resLeft = diffWaysToCompute(expression.substring(0, i));
                List<Integer> resRight = diffWaysToCompute(expression.substring(i + 1));
                // 按运算符结合两个结果集
                for (int j = 0; j < resLeft.size(); j++) {
    
                    for (int k = 0; k < resRight.size(); k++) {
    
                        char operation = expression.charAt(i);
                        res.add(calculate(resLeft.get(j), operation, resRight.get(k)));
                    }
                }
            }
        }
        // 保存到map
        mem.put(expression, res);
        return res;
    }

    private int calculate(int a, char op, int b) {
    
        switch (op) {
    
            case '+' :
                return a + b;
            case '-' :
                return a - b;
            case '*' :
                return a * b;
        }
        return -1;
    }

    private boolean isOperation(char c) {
    
        return !Character.isDigit(c);
    }
}

1.2 动态规划

• 为运算表达式设计优先级

2 Reference

• 为运算表达式设计优先级
• 详细通俗的思路分析，多解法