Simple Recursion (TLE)
We could easily break this problem into subproblems. Whenever we encounter an operator, we simply calculate different ways to solve the expression on its left and different ways to solve the expression on its right. Then, we apply the operator on each such pair of left and right results. Our base case for this recursion would be when the input string does not contain any operator. We would then simply return the number (note that we have to return a vector so we would actually return a vector containing only that number).
vector<int> diffWaysToCompute(string input) {
vector<int> res;
int len = input.length();
for (int i=0; i<len; i++) {
char c = input[i];
if (c=='+' || c=='-' || c=='*') {
vector<int> res1 = diffWaysToCompute(input.substr(0, i));
vector<int> res2 = diffWaysToCompute(input.substr(i+1));
for (int j=0; j<res1.size(); j++) {
for (int k=0; k<res2.size(); k++) {
if (c=='+') {
res.push_back(res1[j]+res2[k]);
} else if (c=='-') {
res.push_back(res1[j]-res2[k]);
} else {
res.push_back(res1[j]*res2[k]);
}
}
}
}
}
// no operator in input string
if (res.size()==0)
return {stoi(input)};
return res;
}
Adding memoization
It is easy to identify with an example that the above recursion has a lot of overlapping subproblems. Memoization comes in handy in such cases. So how do we memoize? Notice that we have to keep track of the vector of resulting numbers for each input string. An appropriate data structure to store such vector for a string value would be a hash table. That’s exactly what we do in the code below.
class Solution {
public:
unordered_map<string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector<int> res;
int len = input.length();
if (memo[input].size()>0) return memo[input];
for (int i=0; i<len; i++) {
char c = input[i];
if (c=='+' || c=='-' || c=='*') {
vector<int> res1 = diffWaysToCompute(input.substr(0, i));
vector<int> res2 = diffWaysToCompute(input.substr(i+1));
for (int j=0; j<res1.size(); j++) {
for (int k=0; k<res2.size(); k++) {
if (c=='+') {
res.push_back(res1[j]+res2[k]);
} else if (c=='-') {
res.push_back(res1[j]-res2[k]);
} else {
res.push_back(res1[j]*res2[k]);
}
}
}
}
}
// no operator in input string
if (res.size()==0)
return memo[input] = {stoi(input)};
return memo[input] = res;
}
};