115. Distinct Subsequences
Description
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s.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.babgbag
babgbag
babgbag
babgbag
babgbag
Constraints:
1 <= s.length, t.length <= 1000
s
andt
consist of English letters.
Solutions
Solution: Dynamic Programming
- Time complexity: O(mn)
- Space complexity: O(mn)
JavaScript
js
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
const numDistinct = function (s, t) {
const memo = new Map();
const dp = (a, b) => {
if (b === t.length) return 1;
if (a === s.length || s.length - a < t.length - b) return 0;
const key = `${a},${b}`;
if (memo.has(key)) return memo.get(key);
let result = dp(a + 1, b);
if (s[a] === t[b]) {
result += dp(a + 1, b + 1);
}
memo.set(key, result);
return result;
};
return dp(0, 0);
};