跳转至

115. 不同的子序列

力扣链接(困难)：https://leetcode.cn/problems/distinct-subsequences

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 1：

Text Only
1
2
3
4
5
6
7
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：

Text Only
1
2
3
4
5
6
7
8
9
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

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

个人题解

动态规划

  • dp[i][j] 表示区间 [0, i - 1] 的 s 子序列中出现区间 [0, j - 1] 的 t 的个数；
  • 初始化 dp：长度为 0 的 t 显然在 s 的子序列中出现次数为 1；长度为 0 的 s 子序列长度也为 0，那么 t 不可能在 s 子序列中出现；
  • 状态转移：当前字符匹配：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，当前字符不匹配：dp[i][j] = dp[i - 1][j]
    • 对于 s[i - 1] == t[j - 1]，即当前位置字符匹配，t 中 [0, j - 1] 部分和 [0, j - 2] 部分的出现次数相同，因为满足 s[i - 1] == t[j - 1] 后，t 前面部分 [0, j - 2] 是在 dp[i - 1][j - 1] 状态的方式下匹配的，所以算作一种匹配方式，即 dp[i][j] = dp[i - 1][j - 1]；
    • 还有一种情况：虽然 s[i - 1] == t[j - 1] 但不将当前字符作为匹配项，而是等待使用 s 后续项进行匹配，即 dp[i - 1][j]；
    • 对于 s[i - 1] != t[j - 1]：同上述的第二种情况。

对于状态转移推导中 s[i - 1] == t[j - 1] 的第二种情况举例说明：

假设 s = "yuelaii", t = "yuelai" 那么显然有两类匹配方式（分别对应上述推导中的两类）：

  1. s 中 [0, 5] 子序列 与 t 匹配；
  2. s 中 [0, 4] 及 s[6] 组成的子序列与 t 匹配。

题解代码

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numDistinct(string s, string t) {
        const int N = 1010;
        // dp[i][j]: 区间[0, i - 1]的 s 子序列中出现区间[0, j - 1]的 t 的个数
        uint32_t dp[N][N] = {};

        // 初始化 dp
        // 长度为 0 的 t 显然在 s 的子序列中出现次数为 1
        for(int i = 0; i < s.size(); i++) dp[i][0] = 1;
        // 长度为 0 的 s 子序列长度也为 0，那么 t 不可能在 s 子序列中出现
        // 注意不要包含 dp[0][0]
        for(int j = 1; j < t.size(); j++) dp[0][j] = 0;

        for(int i = 1; i <= s.size(); i++) {
            for(int j = 1; j <= t.size(); j++) {
                if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j];
            }
        }

        return dp[s.size()][t.size()];
    }
};