# C++ Solution with Memoization

• ``````class Solution {
public:

vector<vector<vector<int> > > Memo;

vector<int> DiffWaysToCompute(const string &input,int s, int e)
{
vector<int> Result;

for(int i = s; i < e; ++i)
{
if(isdigit(input[i]) == false)
{

vector<int> Left; //= DiffWaysToCompute(input,s,i);
vector<int> Right; //= DiffWaysToCompute(input,i + 1,e);

if(Memo[s][i].empty())
{
Left = DiffWaysToCompute(input,s,i);
Memo[s][i] = Left;
}
else
{
Left = Memo[s][i];
}

if(Memo[i + 1][e].empty())
{
Right = DiffWaysToCompute(input,i + 1,e);
Memo[i + 1][e] = Right;
}
else
{
Right= Memo[i + 1][e];
}

for(auto &l : Left)
{
for(auto &r : Right)
{
if(input[i] == '+')
{
Result.push_back(l + r);
}
else if(input[i] == '-')
{
Result.push_back(l - r);
}
else
{
Result.push_back(l * r);
}
}
}
}
}

if(Result.empty())
{
istringstream ss(input.substr(s,e - s));
int Num = 0;
ss >> Num;
Result.push_back(Num);
}

Memo[s][e] = Result;

return (Result);
}

vector<int> diffWaysToCompute(string input)
{

Memo.resize(input.size());

for(int i = 0; i < input.size(); ++i)
{
Memo[i].resize(input.size() + 1);
}

return DiffWaysToCompute(input,0,input.size());
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.