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.
1def numDistinct(s: str, t: str) -> int:
2 m, n = len(s), len(t)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4
5 for i in range(m + 1):
6 dp[i][0] = 1
7
8 for i in range(1, m + 1):
9 for j in range(1, n + 1):
10 if s[i - 1] == t[j - 1]:
11 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
12 else:
13 dp[i][j] = dp[i - 1][j]
14
15 return dp[m][n]
16
17# Example usage
18print(numDistinct("rabbbit", "rabbit"))This Python solution uses a nested list `dp` to store the number of subsequences. The outer loop iterates over each character in `s`, while the inner loop checks each character of `t`, updating the DP table based on whether characters match or not. The result can be found at the last element `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.
This C function reduces space usage by utilizing two arrays, alternating between them to store the current and previous results. The modulo operation helps alternate between using `previous` and `current`, simplifying the 2D structure to two 1D arrays.