LeetCode 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".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]

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

 

Solution:

public List<Integer> diffWaysToCompute(String s) {
    String[] arr = s.split("[\\+\\-\\*\\/]");
    String[] ops = s.split("\\d+"); // Note: the 1st item is a space
    int n = arr.length;
    int[] nums = new int[n];
    for(int i=0; i<n; i++) {
        nums[i] = Integer.parseInt(arr[i].trim());
    }
    return diffWays(nums, ops, 0, n-1);
}

public List<Integer> diffWays(int[] nums, String[] ops, int left, int right) {
    List<Integer> list  = new ArrayList<>();
    if(left == right) {
        list.add(nums[left]);
        return list;
    }
    for(int i=left+1; i<=right; i++) {
        List<Integer> list1 = diffWays(nums, ops, left, i-1);
        List<Integer> list2 = diffWays(nums, ops, i, right);
        for(int num1:list1) {
            for(int num2:list2) {
                switch(ops[i].charAt(0)) {
                    case '+': list.add(num1+num2); break;
                    case '-': list.add(num1-num2); break;
                    case '*': list.add(num1*num2); break;
                    case '/': list.add(num1/num2); break;
                }
            }
        }
    }
    return list;
}