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