# [C++] My primary O(N*M) DP solution using O(N*M) space (poor math)

• Though I'm not very good at math, I finally struggled to get AC.

``````class Solution {
public:
typedef unordered_map<int*, int> Cache;

int numDistinct(string S, string T) {
if (T.empty()) return 1;
if (S.empty() || S.length() < T.length()) return 0;
// collect indexes for each char of T in S
vector<vector<int>> indexes(T.length());
for (int i = 0; i < S.length(); i++) {
for (int j = 0; j < T.length(); j++) {
if (S[i] == T[j]) {
indexes[j].push_back(i);
}
}
}
Cache cache;
// calculate all possible ways to get the next char of T recursively
return countDistinct(indexes, 0, -1, cache);
}
int countDistinct(vector<vector<int>> &indexes, int n, int limit, Cache &cache) {
vector<int> &index = indexes[n];
int sum = 0;
for (int i = index.size() - 1; i >= 0; i--) {
if (index[i] <= limit) break;  // the index of the next char must be bigger
if (n + 1 < indexes.size()) {
auto it = cache.find(&index[i]);
if (it == cache.end()) {
int num = countDistinct(indexes, n + 1, index[i], cache);
cache[&index[i]] = num;
sum += num;
} else {
sum += it->second;
}
} else {
sum++;
}
}
return sum;
}
};``````

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