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.
1using System;
2
3public class Solution {
4 public int NumDistinct(string s, string t) {
5 int m = s.Length, n = t.Length;
6 int[,] dp = new int[m + 1, n + 1];
7
8 for (int i = 0; i <= m; i++) {
9 dp[i, 0] = 1;
10 }
11
12 for (int i = 1; i <= m; i++) {
13 for (int j = 1; j <= n; j++) {
14 if (s[i - 1] == t[j - 1]) {
dp[i, j] = dp[i - 1, j - 1] + dp[i - 1, j];
} else {
dp[i, j] = dp[i - 1, j];
}
}
}
return dp[m, n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.NumDistinct("rabbbit", "rabbit"));
}
}The C# code utilizes a 2D array `dp` to compute the number of subsequences. The nested loops traverse through strings `s` and `t` to fill the DP table that holds intermediate results. The cell `dp[m, n]` yields the count of subsequences of `s` that form `t`.
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.
This JavaScript approach uses two 1D arrays `prev` and `cur`. The main logic involves updating only necessary states per iteration, switching arrays at each outer loop step to retain recent results efficiently.