To solve this problem, we need to find the number of distinct subsequences of a string ( S ) that equal another string ( T ). A subsequence is formed by deleting some characters from ( S ) without changing the order of the remaining characters.
Approach
The key insight here is to use dynamic programming (DP) with space optimization. We can use a 1D DP array where ( dp[j] ) represents the number of ways to form the first ( j ) characters of ( T ) from the characters of ( S ) processed so far.
-
Initialization:
- If ( T ) is empty, return 1 (since there's exactly one way to form an empty subsequence).
- If ( S ) is empty or shorter than ( T ), return 0 (since we can't form a longer string from a shorter one).
- Initialize a DP array of size ( len(T) + 1 ) with ( dp[0] = 1 ) (base case: one way to form an empty subsequence) and all other values as 0.
-
DP Transition:
- For each character in ( S ), iterate over the DP array from the end to the start (to avoid overwriting values we need for subsequent calculations).
- If the current character in ( S ) matches the ( j-1 )-th character in ( T ), update ( dp[j] ) by adding ( dp[j-1] ) (this accounts for including the current character in the subsequence).
Solution Code
def numDistinct(s: str, t: str) -> int:
m, n = len(s), len(t)
if n > m:
return 0
dp = [0] * (n + 1)
dp[0] = 1 # Base case: one way to form empty subsequence
for c in s:
# Iterate from the end to avoid overwriting dp[j-1] before using it
for j in range(n, 0, -1):
if c == t[j-1]:
dp[j] += dp[j-1]
return dp[n]
Explanation
- Initialization: The DP array starts with ( dp[0] = 1 ) because there is exactly one way to form an empty subsequence (by deleting all characters from ( S )).
- Processing Characters: For each character in ( S ), we update the DP array from right to left. This ensures that when we update ( dp[j] ), the value of ( dp[j-1] ) (which we need) hasn't been modified yet in the current iteration.
- Result: The value at ( dp[len(T)] ) gives the number of distinct subsequences of ( S ) that equal ( T ).
This approach efficiently computes the result with a time complexity of ( O(m \times n) ) (where ( m ) is the length of ( S ) and ( n ) is the length of ( T )) and a space complexity of ( O(n) ) (due to the 1D DP array), making it optimal for most cases.
Example: For ( S = "rabbbit" ) and ( T = "rabbit" ), the DP array eventually becomes ( [1,1,1,3,3,3,3] ), so the result is ( dp[6] = 3 ), which is correct.
This solution handles all edge cases and efficiently computes the desired result.


作者声明:本文包含人工智能生成内容。