Question

Formatted question description: https://leetcode.ca/all/241.html

 241	Different Ways to Add Parentheses

 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"
 Output: [0, 2]

 Explanation:
 ((2-1)-1) = 0
 (2-(1-1)) = 2

 Example 2:

 Input: "2*3-4*5"
 Output: [-34, -14, -10, -10, 10]

 Explanation:
 (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

Algorithm

For each operator, divide the input into two parts, left and right, and throw them into recursion to calculate, so you can get two integer arrays left and right, which represent all that can be obtained by adding different parentheses to the two parts’ different values.

At this point, we only need to take numbers from the two arrays to perform the current operator calculation, and then save in the result.

Of course, if the final result res is still empty, then there is only one case, input itself is a number, directly converted to an integer and stored in the result.

Code

Java

  • import java.util.ArrayList;
    import java.util.List;
    
    public class Different_Ways_to_Add_Parentheses {
    
    
        public class Solution {
            public List<Integer> diffWaysToCompute(String input) {
                List<Integer> result = new ArrayList<>();
    
                if (input == null || input.length() == 0) {
                    return result;
                }
    
                for (int i = 0; i < input.length(); i++) {
                    char c = input.charAt(i);
    
                    if (!isOperator(c)) {
                        continue;
                    }
    
                    List<Integer> left = diffWaysToCompute(input.substring(0, i));
                    List<Integer> right = diffWaysToCompute(input.substring(i + 1));
    
                    for (int num1 : left) {
                        for (int num2 : right) {
                            int val = calculate(num1, num2, c);
                            result.add(val);
                        }
                    }
                }
    
                // only contains one number
                if (result.isEmpty()) {
                    result.add(Integer.parseInt(input));
                }
    
                return result;
            }
    
            private int calculate(int num1, int num2, char operator) {
                int result = 0;
    
                switch(operator) {
                    case '+' : result = num1 + num2;
                        break;
    
                    case '-' : result = num1 - num2;
                        break;
    
                    case '*' : result = num1 * num2;
                        break;
                }
    
                return result;
            }
    
            private boolean isOperator(char operator) {
                return (operator == '+') || (operator == '-') || (operator == '*');
            }
        }
    }
    
  • Todo
    
  • from operator import *
    
    
    class Solution(object):
      def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        ops = {"+": add, "-": sub, "*": mul, "/": div}
        ans = []
        for i, c in enumerate(input):
          if c in ops:
            left = self.diffWaysToCompute(input[:i])
            right = self.diffWaysToCompute(input[i + 1:])
            ans.extend([ops[c](a, b) for a in left for b in right])
        return ans if ans else [int(input)]
    
    

All Problems

All Solutions