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

提示：

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

解题思路

这是一道经典的动态规划问题，需要计算字符串 s 的子序列中有多少个等于字符串 t。

思路分析：

定义 dp[i][j] 表示字符串 s 的前 i 个字符中包含字符串 t 的前 j 个字符的子序列个数。

状态转移方程：

  • 当 j = 0 时，dp[i][0] = 1，因为空字符串是任何字符串的子序列
  • 当 i = 0 且 j > 0 时，dp[0][j] = 0，因为空字符串不能包含非空子序列
  • 当 s[i-1] == t[j-1] 时，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    • dp[i-1][j-1]：使用 s[i-1] 匹配 t[j-1]
    • dp[i-1][j]：不使用 s[i-1]，在前面的字符中寻找
  • 当 s[i-1] != t[j-1] 时，dp[i][j] = dp[i-1][j]
    • 只能不使用 s[i-1]，在前面的字符中寻找

优化思路： 可以使用滚动数组优化空间复杂度，但需要注意更新顺序。推荐使用二维数组实现，逻辑更清晰。

代码实现

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.length(), n = t.length();
        vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));
        
        // 空字符串是任何字符串的子序列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
                if (s[i-1] == t[j-1]) {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        
        return dp[m][n];
    }
};

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 空字符串是任何字符串的子序列
        for i in range(m + 1):
            dp[i][0] = 1
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i-1][j]
                if s[i-1] == t[j-1]:
                    dp[i][j] += dp[i-1][j-1]
        
        return dp[m][n]

public class Solution {
    public int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        long[,] dp = new long[m + 1, n + 1];
        
        // 空字符串是任何字符串的子序列
        for (int i = 0; i <= m; i++) {
            dp[i, 0] = 1;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i, j] = dp[i - 1, j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i, j] += dp[i - 1, j - 1];
                }
            }
        }
        
        return (int)dp[m, n];
    }
}

var numDistinct = function(s, t) {
    const m = s.length;
    const n = t.length;
    
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    
    return dp[m][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要填充 m × n 的二维数组
空间复杂度O(m × n)使用二维数组存储状态

注：m 为字符串 s 的长度，n 为字符串 t 的长度。可以优化为 O(n) 空间复杂度。

相关题目