241. Different Ways to Add Parentheses

文章目录

• 1 题目理解
• 2 分治法

1 题目理解

输入：字符串input，包含数字和操作符

规则：给input的不同位置加括号，使得input可以得到不同的计算结果。

输出：返回可能的计算结果

Example 1:

Input: “2-1-1”

Output: [0, 2]

Explanation:

((2-1)-1) = 0

(2-(1-1)) = 2

2 分治法

文章参考力扣官网。

对于形如 x op y 的运算式而言，它的结果取决于 x和y结果的组合数。而 x和y又别分可以写成 x op y 这样的运算式。

因此该问题中的子问题就是 x op y 需要先解决 操作符两侧算式。

1 分解：按照操作符将式子分解为左右两部分

2 解决：递归调用，求得左右两边算式的值

3 合并：根据运算符，计算得到最终解

class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        return compute(input);
    }
    private List<Integer> compute(String input){
        List<Integer> result = new ArrayList<Integer>();
        for(int i=0;i<input.length();i++){
            char op = input.charAt(i);
            if(op=='+' || op=='-' || op=='*' || op=='/'){
                List<Integer> leftValueList = compute(input.substring(0,i));
                List<Integer> rightValueList = compute(input.substring(i+1));
                int value = 0;
                for(int leftValue : leftValueList){
                    for(int rightValue : rightValueList){
                        if(op=='+'){
                            value = leftValue+rightValue;
                        }
                        if(op=='-'){
                            value = leftValue - rightValue;
                        }
                        if(op=='*'){
                            value = leftValue * rightValue;
                        }
                        if(op=='/'){
                            value = leftValue / rightValue;
                        }
                        result.add(value);
                    }
                }
            }
        }
        if(result.isEmpty()){
            result.add(Integer.parseInt(input));
        }
        return result;
    }
}