python实现leetcode之115. 不同的子序列

解题思路

使用缓存避免重复计算
定义一个函数，计算s的某区间包含t的某区间多少次
细节如代码中的注释

115. 不同的子序列

代码

class Solution(object):
    def numDistinct(self, s, t):
        cache = {}
        def dp(s, t, sb, tb, se, te):
            key = (sb, tb, se, te)
            if key not in cache:
                if tb > te: cache[key] = 1  # t的所有字符都看完了
                elif sb > se: cache[key] = 0  # t没看完但是s看完了
                elif se - sb < te - te: cache[key] = 0  # t剩下的比s剩下的长度还长
                elif s[sb] != t[tb]:  # 从生于的s里继续搜索t
                    cache[key] = dp(s, t, sb+1, tb, se, te)
                else: 
                    x = dp(s, t, sb+1, tb+1, se, te)  # case1: s和t都消除匹配的字符
                    y = dp(s, t, sb+1, tb, se, te)    # case2: 保留完整的t继续查找
                    cache[key] = x + y
            return cache[key]
        return dp(s, t, 0, 0, len(s) - 1, len(t) - 1)