/

• 本题难度: Medium/Hard
• Topic: Dynamic Programming

Description

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n^2) time and O(n) memory.

O(n^2) memory is also acceptable if you do not know how to optimize memory.

我的代码

class Solution:    """    @param S: A string    @param T: A string    @return: Count the number of distinct subsequences    """    def numDistinct(self, S, T):        # write your code here        ls = len(S)        lt = len(T)        if lt == 0:            return 1        res = [0 for _ in range(ls)]        for i in range(ls):            if S[i] == T[0]:                res[i] = 1        for i in range(1,lt):            pre_sum = 0            for j in range(ls):                now = res[j]                if S[j] == T[i]:                    res[j] = pre_sum                else:                    res[j] = 0 #忘记更新了                pre_sum += now        return sum(res)

思路

一开始想模仿的思路，初始设定空间复杂度为O(n^2)

“dp[i][j] 对S中S[:i+1]和T[:j+1]有多少种情况，当S[i]==T[j]时，如“rabb”和“rab”等于“r”和“ra”的情况+1”

但是突然发现新增加的元素可能在前面就会有重复，所以应该分成两部分来看，即“ra”在S各个位置的情况+各个位置之后“b”的情况。

然后我模拟了一下res的变化，发现res的变化很有规律，可以in-place更新。所以空间复杂度变成了O(n)

S = "rabbbit", T = "rabbit",           r a b b b i tr          1 0 0 0 0 0 0   1ra         0 1 0 0 0 0 0   1rab        0 0 1 1 1 0 0   3rabb       0 0 0 1 2 0 0   3rabbi      0 0 0 0 0 3 0   3rabbit     0 0 0 0 0 0 3   3

• 时间复杂度: O(mn)
• 空间复杂度: O(n)
• 出错
  忘记更新在S[j] != T[i]时的res[i][j]=0