Distinct occurrences
Given two strings S and T of length n and m respectively. find count of distinct occurrences of T in S as a sub-sequence.
- Time : O(nm)
- Space : O(nm)
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
int dp[8080][101];
int mod = 1e9 + 7;
int helper(string& s, string& t, int i, int j) {
if(j == t.length()) return 1;
if(i == s.length()) return 0;
if(dp[i][j] != -1) return dp[i][j];
int& res = dp[i][j] = helper(s, t, i + 1, j);
if(s[i] == t[j]) res = (res + helper(s, t, i + 1, j + 1)) % mod;
return res;
}
public:
int subsequenceCount(string S, string T) {
memset(dp, -1, sizeof dp);
return helper(S, T, 0, 0);
}
};
|
