Different Ways to Add Parentheses LeetCode solution in C++

1
class Solution {
2
 public:
3
  int stoi1(string &s, int i, int j) {
4
    int num = 0;
5
    for (int k = i; k <= j; k++) {
6
      num = num * 10 + (s[k] - '0');
7
    }
8
    return num;
9
  }
10

11
  vector<int> rec(string &s, int i, int j, vector<vector<vector<int>>> &dp) {
12
    if (dp[i][j].size() > 0) {
13
      return dp[i][j];
14
    }
15
    vector<int> ans;
16
    for (int k = i; k <= j; k++) {
17
      if (s[k] == '+' || s[k] == '*' || s[k] == '-') {
18
        vector<int> v1 = rec(s, i, k - 1, dp);
19
        vector<int> v2 = rec(s, k + 1, j, dp);
20
        for (int m = 0; m < v1.size(); m++) {
21
          for (int n = 0; n < v2.size(); n++) {
22
            if (s[k] == '-') {
23
              ans.push_back(v1[m] - v2[n]);
24
            } else if (s[k] == '*') {
25
              ans.push_back(v1[m] * v2[n]);
26
            } else {
27
              ans.push_back(v1[m] + v2[n]);
28
            }
29
          }
30
        }
31
      }
32
    }
33
    if (ans.empty()) {
34
      ans.push_back(stoi1(s, i, j));
35
    }
36
    return dp[i][j] = ans;
37
  }
38

39
  vector<int> diffWaysToCompute(string expression) {
40
    int n = expression.length() + 1;
41
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
42
    return rec(expression, 0, expression.length() - 1, dp);
43
  }
44
};