distinct_subsequences
1from functools import cache 2 3 4# @leet start 5class Solution: 6 def numDistinct(self, s: str, t: str) -> int: 7 """ 8 This question asks us to find the number of distinct subsequences 9 where t fits into s. 10 This can be done in $O(2^n)$ time, where at every letter, you have two 11 choices depending on whether or not the characters match. 12 13 If the characters do not match, we only increment the pointer to s, 14 because we want to continue the search. 15 16 If the characters do match, we can either increment both or just increment 17 s, so we add up the number of both and return that. 18 19 Finally, the terminating conditions: if we hit the end of t, return 1. 20 Otherwise, if we hit the end of s and we haven't hit the end of t, we return 0. 21 """ 22 23 @cache 24 def dp(i, j): 25 if i == len(s) and j != len(t): 26 return 0 27 if j == len(t): 28 return 1 29 if s[i] == t[j]: 30 return dp(i + 1, j + 1) + dp(i + 1, j) 31 else: 32 return dp(i + 1, j) 33 34 return dp(0, 0) 35 36 37# @leet end 38 39 40def test(): 41 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def numDistinct(self, s: str, t: str) -> int: 8 """ 9 This question asks us to find the number of distinct subsequences 10 where t fits into s. 11 This can be done in $O(2^n)$ time, where at every letter, you have two 12 choices depending on whether or not the characters match. 13 14 If the characters do not match, we only increment the pointer to s, 15 because we want to continue the search. 16 17 If the characters do match, we can either increment both or just increment 18 s, so we add up the number of both and return that. 19 20 Finally, the terminating conditions: if we hit the end of t, return 1. 21 Otherwise, if we hit the end of s and we haven't hit the end of t, we return 0. 22 """ 23 24 @cache 25 def dp(i, j): 26 if i == len(s) and j != len(t): 27 return 0 28 if j == len(t): 29 return 1 30 if s[i] == t[j]: 31 return dp(i + 1, j + 1) + dp(i + 1, j) 32 else: 33 return dp(i + 1, j) 34 35 return dp(0, 0)
def
numDistinct(self, s: str, t: str) -> int:
7 def numDistinct(self, s: str, t: str) -> int: 8 """ 9 This question asks us to find the number of distinct subsequences 10 where t fits into s. 11 This can be done in $O(2^n)$ time, where at every letter, you have two 12 choices depending on whether or not the characters match. 13 14 If the characters do not match, we only increment the pointer to s, 15 because we want to continue the search. 16 17 If the characters do match, we can either increment both or just increment 18 s, so we add up the number of both and return that. 19 20 Finally, the terminating conditions: if we hit the end of t, return 1. 21 Otherwise, if we hit the end of s and we haven't hit the end of t, we return 0. 22 """ 23 24 @cache 25 def dp(i, j): 26 if i == len(s) and j != len(t): 27 return 0 28 if j == len(t): 29 return 1 30 if s[i] == t[j]: 31 return dp(i + 1, j + 1) + dp(i + 1, j) 32 else: 33 return dp(i + 1, j) 34 35 return dp(0, 0)
This question asks us to find the number of distinct subsequences where t fits into s. This can be done in $O(2^n)$ time, where at every letter, you have two choices depending on whether or not the characters match.
If the characters do not match, we only increment the pointer to s, because we want to continue the search.
If the characters do match, we can either increment both or just increment s, so we add up the number of both and return that.
Finally, the terminating conditions: if we hit the end of t, return 1. Otherwise, if we hit the end of s and we haven't hit the end of t, we return 0.
def
test():