【Leetcode】241.为运算表达式设计优先级

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

题目

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:
输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:
输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

方法（分治法）

分治法即”分而治之”，其基本思想为：将一个复杂的问题分解为一些规模较小的相同子问题，递归解决这些子问题，再将子问题的解合并即可得到原问题的解。

因此分治法需要关注三个内容：

  • 分解：将原问题分解为子问题，并递归解决子问题
  • 合并：将子问题的解合并为原问题的解
  • 递归返回条件：为了避免无限分解子问题，需要设置递归返回条件

典型的应用分治法的例子：快速排序、归并排序、二叉树的一些问题（如找出二叉树最大深度、判断二叉树是否平衡）

对于这道题：

  • 分解：我们先将计算一个大运算表达式的原问题，分解为计算左右两个小运算表达式的子问题。之后递归解决子问题、得到子问题的解。
  • 合并：最后根据左右两个小运算表达式之间的符号确定如何对子问题的解进行合并，得到原问题的解。

如何分解子问题呢？
我们以input中每一个运算符为分界，将这个运算符左边和右边分为两个小运算表达式。相当于先计算左右两个小运算表达式（优先级高），再根据这个运算符来合并为原运算表达式的解（优先级低）。

遍历input中所有的运算符，进行上述分治步骤，因此每一个运算符都曾经成为过优先级最低的运算符，这样保证了最后结果的全面性。

注意：如果给定的字符串input只有数字，没有运算符，那结果就是给定的字符串的数字表示。

代码

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
public List<Integer> diffWaysToCompute(String input) {
    List<Integer> res = new ArrayList<>();
    //递归返回条件
    if(input.length() == 0)
        return res;
    //flag记录input中是否含有运算符
    boolean flag = false;
    for(int i = 0; i < input.length(); i++){
        char ch = input.charAt(i);
        if(ch != '+' && ch != '-' && ch != '*')
            continue;
        flag = true;
        //分解：left列表和right列表分别包含左边和右边可能的计算结果
        List<Integer> left = diffWaysToCompute(input.substring(0, i));
        List<Integer> right = diffWaysToCompute(input.substring(i + 1));
        //合并：根据运算符ch将子问题的解合并为原问题的解
        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);
            }
        }
    }
    //处理字符串input中只有数字，没有运算符的情况
    if(!flag) {
        res.add(Integer.valueOf(input));
        return res;
    }
    return res;
}

由于在递归的过程中，会产生大量的重复计算。因此，如果我们将已计算出的结果保存起来，在下次需要这步计算时直接取出结果，就可避免重复计算。这种方式被称为记忆化搜索

以下为记忆化搜索修改后的代码：

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
Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
    List<Integer> res = new ArrayList<>();
    if(input.length() == 0)
        return res;
    if(map.containsKey(input))
        return map.get(input);
    boolean flag = false;
    for(int i = 0; i < input.length(); i++){
        char ch = input.charAt(i);
        if(ch != '+' && ch != '-' && ch != '*')
            continue;
        flag = true;
        List<Integer> left = diffWaysToCompute(input.substring(0, i));
        List<Integer> right = diffWaysToCompute(input.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(!flag) {
        res.add(Integer.valueOf(input));
        map.put(input, res);
        return res;
    }
    map.put(input, res);
    return res;
}