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.
1class Solution {
2 public int numDistinct(String s, String t) {
3 int m = s.length();
4 int n = t.length();
5 int[][] dp = new int[m + 1][n + 1];
6
7 for (int i = 0; i <= m; i++) {
8 dp[i][0] = 1;
9 }
10
11 for (int i = 1; i <= m; i++) {
12 for (int j = 1; j <= n; j++) {
13 if (s.charAt(i - 1) == t.charAt(j - 1)) {
14 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
15 } else {
16 dp[i][j] = dp[i - 1][j];
17 }
18 }
19 }
20 return dp[m][n];
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 System.out.println(sol.numDistinct("rabbbit", "rabbit"));
26 }
27}This Java code defines a class `Solution` with a method `numDistinct` that uses a 2D array `dp` to count the number of subsequences. We iterate over the characters of `s` and `t`, updating the DP table according to the rules described in the approach. The final result is returned from `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.
The Python solution maintains two lists, `prev` and `cur`. The current result is calculated from the previous row (list), and `prev` is updated to `cur` after calculating each row.