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
^^^
Define f(i, j) to be the number of ways that generate
T[0...j) from S[0...i).
For f(i, j) you can always skip S[i-1], but can
only take it when S[i-1] === T[j-1].
f(0, j) = 0, j > 0 // nothing to delete
f(i, 0) = 1 // delete all
f(i, j) = f(i-1, j) + (S[i-1] === T[j-1] ? f(i-1, j-1) : 0)Dynamic array can be used.
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
let numDistinct = function (s, t) {
const lens = s.length;
const lent = t.length;
const dp = new Array(lent + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= lens; i++) {
for (let j = lent; j >= 1; j--) {
if (s[i - 1] === t[j - 1]) {
dp[j] += dp[j - 1];
}
}
}
return dp[lent];
};☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆
☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆