Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Example 1:
Input: S = "rabbbit", T = "rabbit" Output: 3 Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S. (The caret symbol ^ means the chosen letters)
rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ Example 2:
Input: S = "babgbag", T = "bag" Output: 5 Explanation:
As shown below, there are 5 ways you can generate "bag" from S. (The caret symbol ^ means the chosen letters)
babgbag ^^ ^ babgbag ^^ ^ babgbag ^ ^^ babgbag ^ ^^ babgbag ^^^
// 4ms, 99% prefix tree
/*
for each s[i]:
if s[i] == t[j]:
if j == 0: // found a new matching thread
else:
multiply previous with current. dp[j] = dp[j-1] + dp[j]
why reverse iterating t? take "rabbbit" vs "rabbit" for example
otherwise it may overwrite previous values. need to use a temp array to store current values
*/
class Solution {
public:
int numDistinct(string s, string t) {
vector<long long> dp(t.size(), 0);
for (int i = 0; i < s.size(); i++) {
for (int j = t.size()-1; j >=0; j--) {
if (t[j] == s[i]) {
dp[j] += j == 0? 1 : dp[j-1];
}
}
}
return dp.back();
}
};
// 16ms, 36%
// dp
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<long long>> dp(s.size()+1, vector<long long>(t.size()+1, 0));
dp[0][0] = 1;
// t[0] should be able to start matching with any char in s
for (int i = 1; i <= s.size(); i++) {
dp[i][0] = 1;
}
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < t.size(); j++) {
if (s[i] == t[j]) {
dp[i+1][j+1] = dp[i][j] +
dp[i][j+1]; // if s[i-1] didn't match t[j] but s[i-2] matched t[j-1]
// so s[i-1] maybe skipped
} else {
dp[i+1][j+1] = dp[i][j+1]; // even s[i] !+ t[j], still need to carry on
//if s[i-1] matches t[j], so s[i] maybe skipped
}
}
}
return dp[s.size()][t.size()];
}
};
// 32ms, 6%
class Solution {
private:
int nums(const string& s, const string& t, int si, int tj, vector<vector<int>>& dp) {
if (tj >= t.size()) {
dp[si][tj] = 1;
return 1;
}
if (si >= s.size()) {
return 0;
}
if (dp[si][tj] >= 0) {
return dp[si][tj];
}
int t_sz = t.size() - tj;
int res = 0;
for (int i = si; i < s.size(); i++) {
if (s.size() - i < t_sz)
break;
if (s[i] == t[tj]) {
res += nums(s, t, i+1, tj+1, dp);
}
}
dp[si][tj] = res;
return res;
}
public:
int numDistinct(string s, string t) {
vector<vector<int>> dp(s.size()+1, vector<int>(t.size() + 1, -1));
return nums(s, t, 0, 0, dp);
}
};