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;
    }
}