leetcode 241. Different ways to add parentheses design priority for operational expressions (medium)

One 、 The main idea of the topic

label : Divide and conquer

https://leetcode.cn/problems/different-ways-to-add-parentheses

Give you a string of numbers and operators  expression , Combine numbers and operators according to different priorities , Calculate and return the results of all possible combinations . You can In any order Return to the answer .

The generated test case meets its corresponding output value in line with 32 Bit integer range , The number of different results does not exceed 104 .

Example 1：

Input ：expression = "2-1-1"
Output ：[0,2]
explain ：
((2-1)-1) = 0
(2-(1-1)) = 2

Example 2：

Input ：expression = "23-45"
Output ：[-34,-14,-10,-10,10]
explain ：
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

Tips ：

• 1 <= expression.length <= 20
• expression By numbers and operators '+'、'-' and '*' form .
• All integer values in the input expression are in the range [0, 99]

Two 、 Their thinking

Examples in the title 1,input yes "2-1-1" when , There are two situations ,(2-1)-1 and 2-(1-1), Due to the different brackets , The results are different , But if we regard the things in brackets as a black box , Then it becomes ()-1 and 2-(), The final result is closely related to the possible values in brackets , Then again general One o'clock , In fact, it can become () ? () This form , Within the two parentheses are respective expressions , Finally, two integer arrays will be calculated respectively , The question mark in the middle indicates the operator , It can be plus , reduce , Or by . Then the problem becomes to choose two numbers from two arrays to operate , In an instant, it has become a topic we can do. You mu you ？ The black box represented by the left and right parentheses is handed over to recursion to calculate , Like this, it is divided into two lumps pattern It's the famous divide and conquer method Divide and Conquer 了 , It is an artifact that must be mastered .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char ope = expression.charAt(i);
            if (ope == '+' || ope == '-' || ope == '*') {
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        switch (ope) {
                            case '+':
                                ans.add(l + r);
                                break;
                            case '-':
                                ans.add(l - r);
                                break;
                            case '*':
                                ans.add(l * r);
                                break;
                        }
                    }
                }
            }
        }
        if (ans.isEmpty()) {
            ans.add(Integer.valueOf(expression));
        }
        return ans;
    }
}

Four 、 Summary notes

• 2022/7/7 ' , Another week's delay