forked from shichao-an/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution.py
More file actions
16 lines (16 loc) · 431 Bytes
/
solution.py
File metadata and controls
16 lines (16 loc) · 431 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
# @return an integer
def numDistinct(self, S, T):
if len(S) < len(T):
return 0
n = len(S)
m = len(T)
t = [0 for i in range(m + 1)]
t[0] = 1
for i in range(1, n + 1):
# j = m ... 1
for k in range(m):
j = m - k
if S[i - 1] == T[j - 1]:
t[j] += t[j - 1]
return t[m]