[LeetCode] Different ways to add parentheses

Problem statement (link):

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]

Analysis:

This problem statement is a bit misleading (in a good way) so that my first attempt is to construct the different parenthesesed strings, and compute each string individually. This approach is exponential in both space and time complexity.

Now, the problems that ask for "all possible results" is usually solved using DFS approach. Don't get confused about the * operator as it would be treated equivalently as the + and - because of the parentheses. In the end, all the question asks is to find all possible combinations using parentheses.

With that, we could construct the solutions bottom-up. It's exactly the same as Unique Binary Tree II problem if we think each node as an arithmetic string. For instance,  in Example 2, we have the following ways of constructing the solutions:

Recursion Trees:
1)
                                        2 * 3 - 4 * 5
                                      /                     \
                                   2                   3 - 4 * 5
                                                       /             \
                                                     3             4 * 5
                                                                     /     \
                                                                    4      5
2)
                                        2 * 3 - 4 * 5
                                      /                     \
                                 2 * 3                  4 * 5
                                /       \                 /        \
                              2          3            4           5
3) ...
4) ...
5) ...

You get the idea.

Only extra work we need to do is instead of connecting the nodes, we compute each node (arithmetic string). The time complexity is still exponential but the code looks very clean.

Code:

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<>();
        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
                for (Integer int1: diffWaysToCompute(input.substring(0, i))) {
                    for (Integer int2: diffWaysToCompute(input.substring(i+1))) { // i+1: to skip the operator char
                        res.add(c=='+' ? int1+int2 : c=='-' ? int1-int2 : int1*int2);
                    }
                }
            }
        }

        if (res.size()==0)
            res.add(Integer.parseInt(input));
        return res;
    }
}