Given a string S And a string T, Calculated at S In the subsequence of T Number of occurrences .
A subsequence of a string refers to , By deleting some ( It can also be done without deleting ) Character and does not interfere with the relative position of the remaining characters of the new string .( for example ,“ACE” yes “ABCDE” A subsequence of , and “AEC” No )
Example 1:
Input : S = “rabbbit”, T = “rabbit”
Output : 3
explain :
As shown in the figure below , Yes 3 Species can be obtained from S Get in “rabbit” The plan .
( Up arrow sign ^ Indicates the selected letter )
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input : S = “babgbag”, T = “bag”
Output : 5
explain :
As shown in the figure below , Yes 5 Species can be obtained from S Get in “bag” The plan .
( Up arrow sign ^ Indicates the selected letter )
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
Sketch Map :
class Solution:
def numDistinct(self, s: str, t: str) -> int:
if t == "" and s == "":
return 0
if t == "":
return 1
dp = [[0 for i in range (len(s)+1)] for j in range(len(t)+1) ]
for j in range(0,len(s)+1):
dp[0][j] = 1
for i in range(1,len(t)+1):
for j in range(1,len(s)+1):
dp[i][j] = dp[i][j-1]
if s[j-1] == t[i-1]:
dp[i][j] += dp[i-1][j-1]
return dp[-1][-1]