Sponsored
Sponsored
We use a 2D DP table where `dp[i][j]` represents the number of distinct subsequences of `s[0..i-1]` which forms `t[0..j-1]`. The size of the table is `(m+1)x(n+1)` where `m` is the length of `s` and `n` is the length of `t`.
Initialize `dp[0][0]` to 1 because an empty string is a subsequence of itself, and `dp[i][0]` to 1 for all `i`, because an empty `t` is a subsequence of any prefix of `s`. Then, for each character `s[i-1]` and `t[j-1]`, update the DP table as follows:
Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`.
Space Complexity: O(m * n) for the DP table.
1function numDistinct(s, t) {
2 const m = s.length, n = t.length;
3 const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
4
5 for (let i = 0; i <= m; i++) {
6 dp[i][0] = 1;
7 }
8
9 for (let i = 1; i <= m; i++) {
10 for (let j = 1; j <= n; j++) {
11 if (s[i - 1] === t[j - 1]) {
12 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
13 } else {
14 dp[i][j] = dp[i - 1][j];
15 }
16 }
17 }
18
19 return dp[m][n];
20}
21
22// Example usage
23console.log(numDistinct("rabbbit", "rabbit"));This JavaScript solution employs an array of arrays `dp` to store the subsequence counts. Loops iterate over characters in `s` and `t`, filling up `dp` as the given conditions dictate. The result is the value at `dp[m][n]`.
We can optimize the space complexity by observing that to calculate `dp[i][j]`, we only need values from the previous row. Thus, we can use a 2-row approach, maintaining only `previous` and `current` arrays to save space. This reduces the space complexity to O(n), where `n` is the length of `t`.
The transition is similar to the 2D approach but only updates the necessary parts of the `current` array based on the `previous` row.
Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`.
Space Complexity: O(n), using only two rows for DP storage.
#include <string>
int numDistinct(std::string s, std::string t) {
int m = s.size(), n = t.size();
std::vector<long long> prev(n + 1, 0), cur(n + 1, 0);
prev[0] = cur[0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
cur[j] = s[i - 1] == t[j - 1] ? prev[j - 1] + prev[j] : prev[j];
}
prev = cur;
}
return prev[n];
}
int main() {
std::string s = "rabbbit";
std::string t = "rabbit";
std::cout << numDistinct(s, t) << std::endl;
return 0;
}In this C++ version, two vectors `prev` and `cur` are used to hold the number of subsequences for the previous and current states respectively, allowing us to preserve space. After processing each character pair, `prev` is updated to `cur` for the next iteration.