不同的子序列

难度: Hard

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 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

提示：

0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成

注意：本题与主站 115 题相同： https://leetcode-cn.com/problems/distinct-subsequences/

Submission

运行时间: 31 ms

内存: 16.5 MB

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s)<len(t):
            return 0
        if len(s)==len(t):
            return 1 if s==t else 0

        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]
        dp[0][0] = 1
        for i in range(len(s)):
            dp[i][0] = 1
        
        for i in range(len(s)):
            for j in range(len(t)):
                if i>=j:
                    if s[i] == t[j]:
                        dp[i+1][j+1] = dp[i][j]+dp[i][j+1]
                    else:
                        dp[i+1][j+1] = dp[i][j+1]

        return dp[-1][-1]

Explain

这个题解使用了动态规划的方法来解决问题。定义dp数组，其中dp[i][j]表示字符串s的前i个字符中t的前j个字符作为子序列出现的个数。首先，初始化dp[0][0]为1，表示空字符串s可以匹配空字符串t的方式为1种。对于所有i，dp[i][0]也都设置为1，因为空字符串t是任意字符串s的子序列。接着，我们遍历字符串s和t的每个字符，如果s[i]和t[j]相同，那么dp[i+1][j+1]的值应该是dp[i][j]（s[i]参与匹配）加上dp[i][j+1]（s[i]不参与匹配）的总和。如果s[i]和t[j]不同，那么dp[i+1][j+1]的值仅为dp[i][j+1]。最后，dp[len(s)][len(t)]的值就是答案。

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

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

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(s)<len(t):
            return 0  # 如果s比t短，不可能有匹配
        if len(s)==len(t):
            return 1 if s==t else 0  # 如果长度相同，只有当s和t完全一样时才有1种匹配

        dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]  # 创建dp表
        dp[0][0] = 1  # 空s和空t匹配
        for i in range(len(s)):
            dp[i][0] = 1  # 任意s和空t的匹配
        
        for i in range(len(s)):
            for j in range(len(t)):
                if i>=j:  # 确保s的长度不小于t
                    if s[i] == t[j]:
                        dp[i+1][j+1] = dp[i][j] + dp[i][j+1]  # s[i]匹配t[j]
                    else:
                        dp[i+1][j+1] = dp[i][j+1]  # s[i]不匹配t[j]

        return dp[-1][-1]  # 返回整个s和t的匹配数量

Explore

动态规划数组dp[i][j]表示字符串s的前i个字符中包含字符串t的前j个字符作为子序列的不同方式的个数。具体地，dp[i][j]计数了所有可能的从s的前i个字符中选择出t的前j个字符的序列组合，而不改变t中字符的顺序的方式。

初始化dp[i][0]为1是基于这样一个事实：空字符串可以作为任何字符串的子序列，而且仅有一种方式来实现这一点，即不从字符串s中选择任何字符。因此，对于任意长度的s，总有一种方法将空字符串t作为s的子序列，这就是什么也不选择的情况。

当s[i]和t[j]字符相同的时候，我们有两种选择：一是利用这个相同的字符来匹配t中的字符，二是不利用这个相同的字符。如果我们选择利用s[i]来匹配t[j]，那么剩下的任务就是从s的前i个字符中匹配t的前j个字符，这对应的情况数为dp[i][j]。如果我们选择不利用s[i]来匹配t[j]，即使它们相同，那么问题就变成了从s的前i个字符匹配t的前j+1个字符，这对应的情况数为dp[i][j+1]。因此，dp[i+1][j+1]的值应该是这两种选择的总和。