115.py

'''
 Given a string S and a string T, count the number of distinct subsequences of S which equals T.

 A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

 Example 1:

 Input: S = "rabbbit", T = "rabbit"
 Output: 3
 Explanation:

 As shown below, there are 3 ways you can generate "rabbit" from S.
 (The caret symbol ^ means the chosen letters)

 rabbbit
 ^^^^ ^^
 rabbbit
 ^^ ^^^^
 rabbbit
 ^^^ ^^^
'''

classSolution(object):
defnumDistinct(self, s, t):
"""
 :type s: str
 :type t: str
 :rtype: int
 """

row, col=len(s), len(t)

ifcol>row:
return0

dp= [[0for_inrange(col+1)] for_inrange(row+1)]

forrinrange(row+1):
forcinrange(col+1):
ifr==0andc==0:
dp[r][c] =1
elifr==0:
dp[r][c] =0
elifc==0:
dp[r][c] =1
else:
dp[r][c] =dp[r-1][c]
ifs[r-1] ==t[c-1]:
dp[r][c] +=dp[r-1][c-1]
returndp[row][col]