## Leetcode: different subsequences (Python)

A good function 2020-11-13 02:53:46
leetcode different subsequences python

## 1. Title Description

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
^^^
``````

## 2. Ideas  Sketch Map ： ### 2.1 Code

``````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[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]
``````