不同子序列的记忆问题，谁能记住(缓存)下面的代码?

Question

def numDistinct(self, s: str, t: str) -> int:
n = len(s)
m = len(t)
if n<m:
return 0
count = 0
def check(sub, i, length):
nonlocal count
if i>=n:
return 
if length>m:
return
if sub!=t[:length]:
return
if sub==t:
count+=1
return

for j in range(i+1,n):
temp = sub
sub+=s[j]
check(sub, j, length+1)
sub = temp

for i in range(n):
check(s[i], i, 1)
return count

我找不到一个方法来记忆这个，请帮助。问题是找到，给定两个字符串s和t，返回s等于t的不同子序列的个数。

字符串的子序列是在不影响剩余字符相对位置的情况下，通过删除某些字符(可以不删除)而从原字符串形成的新字符串。

Answer 1

目前您的check函数仅用于副作用，而memoization应用于"纯粹"。没有副作用的函数，并根据其返回值运行。

幸运的是，您的check函数可以很容易地更改为一个纯函数，因为它唯一的副作用是添加到count变量:而不是直接修改计数，它可以返回count应该被更改的数量。现在可以使用functools.lru_cache或functools.cache装饰器(https://docs.python.org/3/library/functools.html#functools.cache)来记忆函数。

from functools import lru_cache
def numDistinct(self, s: str, t: str) -> int:
n = len(s)
m = len(t)
if n<m:
return 0
count = 0
@lru_cache
def check(sub, i, length):
if i>=n:
return 0
if length>m:
return 0
if sub!=t[:length]:
return 0
if sub==t:
return 1

local_count = 0
for j in range(i+1,n):
temp = sub
sub+=s[j]
local_count += check(sub, j, length+1)
sub = temp
return local_count

for i in range(n):
count += check(s[i], i, 1)
return count
print(numDistinct(None, 'foobar', 'for'))