我写的一坨屎,超时了
class Solution:
def numDistinct(self, s, t):
def find_all(a, b, i):
while i < len(a):
j = a.find(b, i)
yield j
if j == -1:
break
i = j + 1
def helper(i, j):
res = 0
print(i, j)
if j == len(t):
return 1
for k in find_all(s, t[j], i):
if k != -1:
res += helper(k+1, j+1)
return res
return helper(0, 0)
递归,超时
时间复杂度:O(2^m^)
空间复杂度:O(1)
class Solution:
def numDistinct(self, s, t):
if len(t) == 0:
return 1
if len(s) == 0:
return 0
if s[-1] == t[-1]:
return self.numDistinct(s[:-1], t[:-1]) + self.numDistinct(s[:-1], t)
else:
return self.numDistinct(s[:-1], t)
动态规划
时间复杂度:O(mn)
空间复杂度:O(mn)
下不下去。。。了。。。
近期评论