-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0115 [H] Distinct Subsequences
Code with Senpai edited this page Jun 19, 2022
·
2 revisions
class Solution:
def numDistinct(self, s: str, t: str) -> int:
@cache
def dp(i, j) -> int:
if j == len(t):
return 1
if i == len(s): # exhausted the source without matching the target
return 0
skip = delete = dp(i+1, j) # delete or skip past the source, but still have to find the char in the target
match = dp(i+1, j+1) # can increment both source and target
if s[i] == t[j]:
res = match + skip # or
else:
res = delete
return res
return dp(0, 0)
footer