Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of S which equals T. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Constraints:
- 1 <= S.length, T.length <= 100
- S and T consist only of lowercase English letters
Examples:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation: There are 3 different ways the substring "rabbit" could be formed from the string "rabbbit". They are listed below in different colors: <font color="red">r</font>ab<font color="red">b</font>bit, <font color="red">ra</font>b<font color="red">b</font>bit, <font color="red">rab</font>b<font color="red">b</font>it.
Solutions
Dynamic Programming
The dynamic programming approach involves creating a 2D array dp where dp[i][j] represents the number of distinct subsequences of the first i characters of S that equals the first j characters of T. The base case is when j is 0, in which case there is only one way to form an empty string from any string, which is to delete all characters. Then, for each character in S, we check if it matches the current character in T. If it does, we have two options: either include the current character in the subsequence or not. If it does not match, we can only not include the current character in the subsequence.
def numDistinct(S, T):
m, n = len(S), len(T)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
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]Follow-up:
What if the strings S and T are very large and we need to optimize the space complexity?
