1. question: 不同的子序列（困难）
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）
题目数据保证答案符合 32 位带符号整数范围。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/distinct-subsequences
示例 1：
1
2
3
4
5
6
7
| 输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
|
示例 2：
1
2
3
4
5
6
7
8
9
| 输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
|
提示：
1
2
| 0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
|
2. answers
参考题解，这道题和判断子序列还是有区别的。判断子序列仅仅是判断是否是子序列，而本题除了判断是否是子序列之外，还要判断次数【这里的次数就是母串s可以找到多少个子序列，且子序列就是该子串t】。下面以一个小例子说明一下：
当判断“acbb”包含几个“acb”时，因为在遍历到各自的最后一个字符时，因为b=b，所以，acbb中最后一个b可以参加匹配，也可不参加匹配，【这里说的参加匹配，指的是是否匹配子串字符】，即出现了两种情况：
- 不参加匹配：“acb”包含几个“acb”，【因为不参加匹配，所以子串中完整无损】
- 参加匹配：“acb”包含几个“ac”，【因为参加匹配，所以子串中也要去掉匹配的字符】
显然“acbb”包含“acb”的子序列就是由上面两种情况总和组成，即1+1=2。同样上面的两种情况，也由该情况的子串组成。
当“acbb”中的b不等于“acb”中的b时，就类似上面的“acb”和“ac”比较，显然，因为“ac”是基准，所以只能是将b删掉，取决于“ac”包含了几个“ac”的情况。
本质上，因为要计算次数，所以同一个字符是否参与匹配就称为了关键。总体来看，和判断子序列类似，只不过定义的数组dp[i][j]不再表示子序列的长度，而是s[i]结尾的子串包含t[j]结尾的子串的子序列的个数。并且状态转移方程也不同。代码如下所示：
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| public class Solution_0142 {
public int numDistinct(String s, String t) {
if(t.length() == 0) return 1;
if(s.length() == 0) return 0;
int[][] dp = new int[s.length()][t.length()];
if(s.charAt(0) == t.charAt(0)) dp[0][0] = 1;
else dp[0][0] = 0;
for (int i = 1; i < t.length(); i++) {
dp[0][i] = 0;
}
for (int i = 1; i < s.length(); i++) {
if(s.charAt(i) == t.charAt(0)) dp[i][0] = dp[i-1][0] + 1;
else dp[i][0] = dp[i-1][0];
}
for (int i = 1; i < s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if(s.charAt(i) == t.charAt(j)) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else dp[i][j] = dp[i-1][j];
}
}
return dp[s.length() - 1][t.length() - 1];
}
public static void main(String[] args) {
System.out.println();
Solution_0142 s0142 = new Solution_0142();
String s = "babgbag";
String t = "bag";
System.out.println(s0142.numDistinct(s, t));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
