leetcode刷题笔记-115.不同的子序列

题目

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

image.png

思路

先注意审题，本题需要求s的子序列中t出现的次数，即t多少次完整的出现在了s的某个子序列中。如果不考虑时间复杂度，其实我们可以用回溯把s的所有长度等于t的子序列都列出来，然后再判断是否有和t相同的子序列。

但很明显，这样写时间复杂度报表了，所以还是用动态规划的思路解题。

第一步是确定dp数组，类似的题目已经写过很多遍了，dp数组的定义都大差不差。

  • dp[i][j]含义：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

然后是确定递推的公式，对于这种子序列匹配的题目，都是分为两种情况

  • s[i-1] == t[j-1]：此时代表s的子序列可以被扩张，也可以选择不扩张，dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
  • s[i-1] != t[j-1]：此时代表s的子序列不能扩张，只能沿用“上一次”的结果，因为是在s的子序列中找t，我们不能从t中删除元素，所以“上一次”的结果只有dp[i-1][j];

这里对第一种s[i-1] == t[j-1]二者相同的情况做说明，为什么会出现“可以扩张，也可以不扩张”呢？

  • 扩张的情况：二者相等，说明当前可能出现t的子序列数量和dp[i-1][j-1]是一致的，因为s[i-1]和t[j-1]这两个字母不需要考虑（这两个字母是相等的，相当于我们从匹配结果中忽略这两个字符，最终得到的子序列的个数也是一样的）。
  • 不扩张的情况：二者相等，我们不一定需要用s[i-1]来扩张子序列。
    • 比如s是bagg，t是bag的情况，s[3]==t[2]，如果我们使用s[3]，最终的子序列是s[0][1][3]；如果不使用s[3]，最终的子序列是s[0][1][2]，这两个子序列都等于t，都是可行的结果。此时使用dp[i-1][j]，相当于我们不用s[3]去构造子序列，而是沿用了s字符串中前一位的结果，说不定不用这个s[i-1]，之前的结果中也能和当前的t[j-1]完整匹配出一个子序列呢？
    • 如果不加上不扩张情况的这个值，相当于漏掉了这种可能性，最终得到的答案肯定是错误的。注意dp的递推一直都是有一个依赖关系的，假设s[0][1][2]这个匹配项不存在，那么dp[i-1][j]会是0，也就不会影响当前的结果。

把这两种情况都考虑上，才是正确的推导公式。

1
2
3
4
5
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];
}

根据推导公式，遍历自然是从小到大遍历，且i和j都依赖于i-1/j-1，所以遍历的时候需要从下标1开始遍历。

我们还需要对下标0的位置进行初始化，分别是i=0和j=0的情况

  • i为0：代表s字符串为空，此时没有任何办法匹配出t字符串，所以i为0的位置需要初始化为0；
  • j为0：代表t字符串为空，此时s字符串可以删除所有元素形成一个空的子序列和t进行匹配，即j为0的位置都须初始化为1；
  • 特殊情况：i和j都为0，此时就是空来匹配空，所以也是初始化为1；

初始化也搞定了，直接遍历使用递推公式就OK啦！

代码

完整代码如下，注意数组中元素需要使用无符号的64位整型，不然会出现计算溢出的情况。最后返回结果的时候需要按题目的要求进行取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int numDistinct(string s, string t) {
        if (s.size() < t.size()) {
            return 0;
        }
        // dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
        vector<vector<uint64_t>> dp(s.size() + 1,
                                     vector<uint64_t>(t.size() + 1, 0));
        // 初始化，分为j=0还有i=0的情况，我们只需要手动处理j=0的情况；
        // 此时s不管多长都可以删除所有元素构成一个空字符串，所以结果应该是1
        for (int i = 0; i < dp.size(); i++) {
            dp[i][0] = 1;
        }
        // 开始遍历
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[i].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];
                }
            }
        }
        // 最终dp数组右下角的就是结果，完整的t和完整的s
        return dp[s.size()][t.size()] % 1000000007;
    }
};

image.png