LeetCode241-为运算表达式设计优先级

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/different-ways-to-add-parentheses/

中文链接：https://leetcode-cn.com/problems/different-ways-to-add-parentheses/

题目详述

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

示例 1:

1
2
3
4
5
输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

1
2
3
4
5
6
7
8
输入: "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

题目详解

分治。

  • 以运算符为分隔符，把表达式分为左右两部分，递归进行处理。
  • 然后把左右两个子过程的结果组合处理，可以得到所有可能的结果。
  • 注意递归终止的条件，表达式只有数字而不含运算符，将表达式直接加入结果链表后返回。
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
public class LeetCode_00241 {

    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); ++i) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                // 递归调用，分为左右两部分
                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 (c == '+') {
                            res.add(l + r);
                        } else if (c == '-') {
                            res.add(l - r);
                        } else {
                            res.add(l * r);
                        }
                    }
                }
            }
        }
        // 为空直接加上对应的数值
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        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
35
36
37
38
39
40
41
42
public class LeetCode_00241 {

    // 运用备忘录方法进行优化
    public List<Integer> diffWaysToCompute(String input) {
        Map<String, List<Integer>> map = new HashMap<>();
        return compute(input, map);
    }

    private List<Integer> compute(String input, Map<String, List<Integer>> map) {
        // 备忘录中存在则直接返回
        if (map.containsKey(input)) {
            return map.get(input);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length(); ++i) {
            char c = input.charAt(i);
            if (c == '+' || c == '-' || c == '*') {
                // 递归调用，分为左右两部分
                List<Integer> left = compute(input.substring(0, i), map);
                List<Integer> right = compute(input.substring(i + 1), map);
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') {
                            res.add(l + r);
                        } else if (c == '-') {
                            res.add(l - r);
                        } else {
                            res.add(l * r);
                        }
                    }
                }
            }
        }
        // 为空直接加上对应的数值
        if (res.size() == 0) {
            res.add(Integer.valueOf(input));
        }
        // 添加入备忘录
        map.put(input, res);
        return res;
    }
}