不同的子序列

标签: 字符串 动态规划

难度: Hard

给你两个字符串 s t ,统计并返回在 s子序列t 出现的个数,结果需要对 109 + 7 取模。

示例 1:

输入:s = "rabbbit", t = "rabbit"
输出3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案rabbbit
rabbbit
rabbbit

示例 2:

输入:s = "babgbag", t = "bag"
输出5
解释:
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案babgbag
babgbag
babgbag
babgbag
babgbag

提示:

  • 1 <= s.length, t.length <= 1000
  • st 由英文字母组成

Submission

运行时间: 32 ms

内存: 0.0 MB

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        
        if m < n: return 0
        if m == n: return 1 if s == t else 0
        
        dp = [0 for _ in range(n)]
        for i in range(m):
            for j in range(n-1, -1, -1):
                if s[i] == t[j]:
                    dp[j] += 1 if j == 0 else dp[j-1]
        return dp[-1]

Explain

这个题解使用动态规划的思路来解决问题。定义一个dp数组,其中dp[j]表示s的前i个字符中,t的前j个字符出现的次数。遍历s的每个字符,对于每个字符,倒序遍历t的字符。如果s[i]等于t[j],那么更新dp[j]的值,dp[j]等于dp[j]加上dp[j-1]的值(如果j等于0,直接加1)。最后返回dp数组的最后一个元素即可。

时间复杂度: O(m*n)

空间复杂度: O(n)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        
        # 如果s的长度小于t,直接返回0
        if m < n: return 0
        # 如果s和t长度相等,判断是否相等,相等返回1,不相等返回0
        if m == n: return 1 if s == t else 0
        
        # 初始化dp数组,长度为n,初始值为0
        dp = [0 for _ in range(n)]
        # 遍历s的每个字符
        for i in range(m):
            # 倒序遍历t的每个字符
            for j in range(n-1, -1, -1):
                # 如果s[i]等于t[j]
                if s[i] == t[j]:
                    # 如果j等于0,dp[j]加1,否则dp[j]加上dp[j-1]的值
                    dp[j] += 1 if j == 0 else dp[j-1]
        # 返回dp数组的最后一个元素
        return dp[-1]

Explore

在这个问题中,我们使用一维数组代替二维数组主要是为了节省空间。如果使用二维数组,我们需要一个大小为m*n的数组来存储状态,其中m和n分别是字符串s和t的长度。然而,观察到每次更新dp数组时,只需要当前行和前一行的数据。因此,通过使用一维数组并以适当的方式更新它,我们只保留必需的信息,从而将空间复杂度从O(m*n)减少到O(n)。

在动态规划的更新过程中,从后向前更新dp数组是为了保证在计算dp[j]的值时,所依赖的dp[j-1]的值是上一轮循环的结果,即前一个状态的值。如果从前向后更新,那么在计算dp[j]时,dp[j-1]可能已经被更新为当前轮的值,这会导致错误地重复计算,从而使得最终结果不正确。因此,倒序更新确保了每个状态是基于正确的前一状态进行计算的。

如果s和t的长度相等,那么问题简化为判断两个字符串是否完全相同。因为动态规划的目的是计算s的子序列中t出现的次数,如果长度相同,那么t只有在完全匹配s的情况下才能被视为一个子序列。这种情况下,没有必要进行复杂的动态规划计算,直接比较两个字符串是否相等即可。如果相等,结果为1;如果不相等,结果为0。这种方法更直接且效率更高。

在动态规划中,dp[j]代表s的前i个字符中,t的前j个字符作为子序列出现的次数。当我们在s中找到一个与t中第j个字符相匹配的字符时,这个字符可以独立形成一个新的子序列(如果j为0),或者它可以扩展所有以t的前j-1个字符结尾的子序列。因此,dp[j]增加dp[j-1]的值表示当前字符可以添加到所有以t的前j-1个字符结尾的子序列末尾,从而形成新的子序列。这是一个累积过程,其中每个匹配都可能增加多个有效子序列的计数。