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.
1#include <stdio.h>
2#include <string.h>
3
4int numDistinct(char* s, char* t) {
5 int m = strlen(s);
6 int n = strlen(t);
7 int dp[m + 1][n + 1];
8
9 for (int i = 0; i <= m; i++) {
10 dp[i][0] = 1;
11 }
12 for (int j = 1; j <= n; j++) {
13 dp[0][j] = 0;
14 }
15
16 for (int i = 1; i <= m; i++) {
17 for (int j = 1; j <= n; j++) {
18 if (s[i - 1] == t[j - 1]) {
19 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
20 } else {
21 dp[i][j] = dp[i - 1][j];
22 }
23 }
24 }
25 return dp[m][n];
26}
27
28int main() {
29 char s[] = "rabbbit";
30 char t[] = "rabbit";
31 printf("%d\n", numDistinct(s, t));
32 return 0;
33}This C code uses a two-dimensional array `dp` where dp[i][j] contains the number of ways the first `i` characters of `s` can form the first `j` characters of `t`. We initialize the first column (except `dp[0][0]`) to 1 because the empty string `t` is a subsequence of any string `s`. We fill the DP table according to the conditions based on whether the current characters of `s` and `t` match or not, then return the value at dp[m][n], which contains the number of distinct subsequences.
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.
public class Solution {
public int NumDistinct(string s, string t) {
int m = s.Length, n = t.Length;
int[] prev = new int[n + 1];
int[] cur = new int[n + 1];
prev[0] = cur[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (s[i] == t[j]) {
cur[j + 1] = prev[j] + prev[j + 1];
} else {
cur[j + 1] = prev[j + 1];
}
}
Array.Copy(cur, prev, n + 1);
}
return prev[n];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.NumDistinct("rabbbit", "rabbit"));
}
}In C#, the space-efficient approach uses two integer arrays `prev` and `cur`, alternating results for each row. The result is stored in `prev[n]` after iterating through characters of `s` and `t`.