1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int numDistinct(string s, string t) {
const int m = s.size(), n = t.size();
if (m < n) return 0;
vector<vector<long>> dp(m + 1, vector<long>(n + 1));
for (int i = 0; i <= m; ++i)
dp[i][n] = 1;
for (int i = m - 1; i >= 0; --i)
for (int j = n - 1; j >= 0; --j)
dp[i][j] = dp[i + 1][j] + (s[i] == t[j] ? dp[i + 1][j + 1] : 0);
return dp[0][0];
}
};
|