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 = "2

3-4

5" Output ：[-34,-14,-10,-10,10] explain ：(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

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  &quot;2-1-1&quot;  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