125.py

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] 

# Time: O(N^2)
# Space: O(N^2)