115. 不同的子序列

🔴   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

Given two strings s and t, return the number of distinct subsequencesof s which equals t.

The test cases are generated so that the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"

Output: 3

Explanation:

As shown below, there are 3 ways you can generate "rabbit" from s.

rabb b** it**

ra b** bbit**

rab b** bit**

Example 2:

Input: s = "babgbag", t = "bag"

Output: 5

Explanation:

As shown below, there are 5 ways you can generate "bag" from s.

ba b g bag

ba bgba** g**

b abgb** ag**

ba b gb ag

babg** bag**

Constraints:

• 1 <= s.length, t.length <= 1000
• s and t consist of English letters.

题目大意

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

示例 1：

输入： s = "rabbbit", t = "rabbit"

输出：3

解释：

如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。

rabb b** it**

ra b** bbit**

rab b** bit**

示例 2：

输入： s = "babgbag", t = "bag"

输出：5

解释：

如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。

ba b g bag

ba bgba** g**

b abgb** ag**

ba b gb ag

babg** bag**

提示：

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

解题思路

1. 定义 dp[i][j]：

   • dp[i][j] 代表 前 i 个字符的 s 中，前 j 个字符的 t 出现的子序列个数。

2. 初始化：

   • dp[i][0] = 1（空字符串 t 是 s 的一个子序列）。
   • dp[0][j] = 0（非空 t 不能从空 s 形成）。

3. 状态转移：

   • 如果 s[i-1] == t[j-1]，两种选择：
     • 取 s[i-1]：dp[i-1][j-1]
     • 不取 s[i-1]：dp[i-1][j]
     • 状态方程： dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
   • 否则：
     • 不能匹配 t[j-1]，只能继承 dp[i-1][j]： dp[i][j] = dp[i-1][j]

4. 滚动数组优化：

   • dp[i][j] 只依赖 dp[i-1][j] 和 dp[i-1][j-1]，可以用 一维数组 降低空间复杂度到 O(n)。

复杂度分析

• 时间复杂度：O(m * n)，双层循环遍历 s 和 t。
• 空间复杂度：O(m * n)，dp 数组存储子序列数量，可以用 一维数组 降低空间复杂度到 O(n)。

代码

动态规划

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
	const m = s.length,
		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];
};

滚动数组优化

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var numDistinct = function (s, t) {
	const m = s.length,
		n = t.length;
	let dp = new Array(n + 1).fill(0);
	dp[0] = 1;

	for (let i = 1; i <= m; i++) {
		for (let j = n; j > 0; j--) {
			if (s[i - 1] === t[j - 1]) {
				dp[j] += dp[j - 1];
			}
		}
	}
	return dp[n];
};

相关题目

题号	标题	题解	标签	难度	力扣
1987	不同的好子序列数目		字符串 动态规划	🔴	🀄️ 🔗