241. Different Ways to Add Parentheses (Medium)

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]

Solution 1: Divide and Conquer 3ms

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> res;
        for (int i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> left = diffWaysToCompute(input.substr(0, i));
                vector<int> right = diffWaysToCompute(input.substr(i+1));
                for (int j = 0; j < left.size(); ++j) {
                    for (int k = 0; k < right.size(); ++k) {
                        if (input[i] == '+') res.push_back(left[j]+right[k]);
                        else if (input[i] == '-') res.push_back(left[j]-right[k]);
                        else res.push_back(left[j]*right[k]);
                    }
                }
            }
        }
        if (res.empty()) res.push_back(stoi(input));
        return res;
    }
};

Solution 2: DP

There are many repeating subquestions in this recursive method, therefore, we could use dynamic programming to avoid this situation by saving the results for subquestions. Here is the DP solution.

class Solution {
    vector<int> helper(string input, unordered_map<string, vector<int>>& dp) {
        vector<int> res;
        for (int i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                string s1 = input.substr(0,i), s2 = input.substr(i+1);
                vector<int> left = dp.count(s1) ? dp[s1]:helper(s1, dp);
                vector<int> right = dp.count(s2) ? dp[s2]:helper(s2, dp);
                for (auto a: left) {
                    for (auto b: right) {
                        if (input[i] == '+') res.push_back(a+b);
                        else if (input[i] == '-') res.push_back(a-b);
                        else res.push_back(a*b);
                    }
                }
            }
        }

        if (res.empty()) res.push_back(stoi(input));
        // save to dpMap
        dp[input] = res;
        return res;
    }
public:
    vector<int> diffWaysToCompute(string input) {
        unordered_map<string, vector<int>> dp;
        return helper(input, dp);
    }
};