leetcode241.Different Ways to Add Parentheses

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. 
The valid operators are +, - and *.


Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]


Example 2
Input: "2*3-4*5"

(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
Output: [-34, -14, -10, -10, 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public List<Integer> diffWaysToCompute(String input) {
    return diffWaysToCompute(input, 0, input.length());
}

public List<Integer> diffWaysToCompute(String input, int startIndex, int endIndex){
    boolean isDigit = true;
    List<Integer> result = new ArrayList<Integer>();
    for(int i = startIndex ; i<endIndex ; i++){
        char cur = input.charAt(i);
        if(cur == '+' || cur == '-' || cur=='*' ){
            isDigit = false;
            List<Integer> leftValue = diffWaysToCompute(input, startIndex, i);
            List<Integer> rightValue = diffWaysToCompute(input, i+1, endIndex);
            result.addAll(compute(leftValue, rightValue,cur));
        }
    }
    if(isDigit){
        result.add(Integer.parseInt(input.substring(startIndex, endIndex)));
    }
    return result;
}

public List<Integer> compute(List<Integer> leftValue, List<Integer> rightValue, char operator){
    switch(operator){
    case '+' : return add(leftValue, rightValue);
    case '-' : return minus(leftValue, rightValue);
    case '*' : return multiply(leftValue, rightValue);
    }
    return new ArrayList<>();
}

public List<Integer> add(List<Integer> leftValue, List<Integer> rightValue){
    List<Integer> result = new ArrayList<Integer>();
    for(int left : leftValue){
        for(int right : rightValue){
            result.add(left + right);
        }
    }
    return result;
}

public List<Integer> minus(List<Integer> leftValue, List<Integer> rightValue){
    List<Integer> result = new ArrayList<Integer>();
    for(int left : leftValue){
        for(int right : rightValue){
            result.add(left - right);
        }
    }
    return result;
}

public List<Integer> multiply(List<Integer> leftValue, List<Integer> rightValue){
    List<Integer> result = new ArrayList<Integer>();
    for(int left : leftValue){
        for(int right : rightValue){
            result.add(left * right);
        }
    }
    return result;
}

提高性能的方法是通过Map实现缓存。将已经遍历过的结果存入缓存中，如果碰到重复的计算式，就可以直接获取其所有可能的值。

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
Map<String, List<Integer>> cache = new HashMap<String, List<Integer>>();
public List<Integer> diffWaysToCompute_withCache(String input){
    if(cache.containsKey(input)) return cache.get(input);
    List<Integer> result = new ArrayList<Integer>();
    boolean isDigit = true;
    for(int i = 0 ; i<input.length() ; i++){
        int cur = input.charAt(i);
        if(cur == '+' || cur == '-' || cur == '*'){
            isDigit = false;
            List<Integer> leftValues = diffWaysToCompute_withCache(input.substring(0, i));
            List<Integer> rightValues = diffWaysToCompute_withCache(input.substring(i+1));
            for(Integer left : leftValues){
                for(Integer right : rightValues){
                    switch(cur){
                    case '+' : result.add(left + right); break;
                    case '-' : result.add(left - right); break;
                    case '*' : result.add(left * right); break;
                    }
                }
            }
        }
    }
    if(isDigit){ result.add(Integer.parseInt(input));}
    cache.put(input, result);
    return result;
}