Distinct subsequences
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
@cache
def dp(i, j):
if j == n:
return 1
if n - j > m - i:
return 0
res = 0
if s[i] == t[j]:
res += dp(i + 1, j + 1) + dp(i + 1, j)
else:
res += dp(i + 1, j)
return res
return dp(0, 0)
Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s.rabbbitrabbbitrabbbit
Example 2:
Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s.babgbagbabgbagbabgbagbabgbagbabgbag
Constraints:
1 <= s.length, t.length <= 1000sandtconsist of English letters.