前言

代码随想录算法训练营day55

一、Leetcode 392.判断子序列

1.题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如，"ace"是"abcde"的一个子序列，而"aec"不是)。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc" 输出：true

示例 2：

输入：s = "axc", t = "ahbgdc" 输出：false

提示：

1. 0 <= s.length <= 100
2. 0 <= t.length <= 10^4
3. 两个字符串都只由小写字符组成。

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/is-subsequence

2.解题思路

方法一：双指针

思路及算法

本题询问的是，ss 是否是 tt 的子序列，因此只要能找到任意一种 ss 在 tt 中出现的方式，即可认为 ss 是 tt 的子序列。

而当我们从前往后匹配，可以发现每次贪心地匹配靠前的字符是最优决策。

假定当前需要匹配字符 cc，而字符 cc 在 tt 中的位置 x1x1 和 x2x2 出现(x1<x2x1<x2)，那么贪心取 x1x1 是最优解，因为 x2x2 后面能取到的字符，x1x1 也都能取到，并且通过 x1x1 与 x2x2 之间的可选字符，更有希望能匹配成功。

这样，我们初始化两个指针 ii 和 jj，分别指向 ss 和 tt 的初始位置。每次贪心地匹配，匹配成功则 ii 和 jj 同时右移，匹配 ss 的下一个位置，匹配失败则 jj 右移，ii 不变，尝试用 tt 的下一个字符匹配 ss。

最终如果 ii 移动到 ss 的末尾，就说明 ss 是 tt 的子序列。

3.代码实现

```java class Solution { public boolean isSubsequence(String s, String t) { int n = s.length(), m = t.length(); int i = 0, j = 0; while (i < n && j < m) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == n; } }
```

二、Leetcode 115.不同的子序列

1.题目

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

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit" 输出：3 解释： 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。 rabbbit rabbbit rabbbit

示例 2：

输入：s = "babgbag", t = "bag" 输出：5 解释： 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 babgbag babgbag babgbag babgbag babgbag

提示：

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

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/distinct-subsequences

2.解题思路

方法一：动态规划

假设字符串 ss 和 tt 的长度分别为 mm 和 nn。如果 tt 是 ss 的子序列，则 ss 的长度一定大于或等于 tt 的长度，即只有当 m≥nm≥n 时，tt 才可能是 ss 的子序列。如果 m

当 m≥nm≥n 时，可以通过动态规划的方法计算在 ss 的子序列中 tt 出现的个数。

创建二维数组 dpdp，其中 dp[i][j]dp[i][j] 表示在 s[i:]s[i:] 的子序列中 t[j:]t[j:] 出现的个数。

上述表示中，s[i:]s[i:] 表示 ss 从下标 ii 到末尾的子字符串，t[j:]t[j:] 表示 tt 从下标 jj 到末尾的子字符串。

考虑动态规划的边界情况：

1. 当 j=nj=n 时，t[j:]t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m0≤i≤m，有 dp[i][n]=1dp[i][n]=1；
2. 
3. 当 i=mi=m 且 j<nj<n 时，s[i:]s[i:] 为空字符串，t[j:]t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 0≤j<n0≤j<n，有 dp[m][j]=0dp[m][j]=0。

当 i

1. 当 s[i]=t[j]s[i]=t[j] 时，dp[i][j]dp[i][j] 由两部分组成：
2. 
3.     如果 s[i]s[i] 和 t[j]t[j] 匹配，则考虑 t[j+1:]t[j+1:] 作为 s[i+1:]s[i+1:] 的子序列，子序列数为 dp[i+1][j+1]dp[i+1][j+1]；
4. 
5.     如果 s[i]s[i] 不和 t[j]t[j] 匹配，则考虑 t[j:]t[j:] 作为 s[i+1:]s[i+1:] 的子序列，子序列数为 dp[i+1][j]dp[i+1][j]。
6. 
7. 因此当 s[i]=t[j]s[i]=t[j] 时，有 dp[i][j]=dp[i+1][j+1]+dp[i+1][j]dp[i][j]=dp[i+1][j+1]+dp[i+1][j]。
8. 
9. 当 s[i]≠t[j]s[i]=t[j] 时，s[i]s[i] 不能和 t[j]t[j] 匹配，因此只考虑 t[j:]t[j:] 作为 s[i+1:]s[i+1:] 的子序列，子序列数为 dp[i+1][j]dp[i+1][j]。
10. 
11. 因此当 s[i]≠t[j]s[i]=t[j] 时，有 dp[i][j]=dp[i+1][j]dp[i][j]=dp[i+1][j]。

由此可以得到如下状态转移方程：

dp[i][j]={dp[i+1][j+1]+dp[i+1][j],s[i]=t[j]dp[i+1][j],s[i]≠t[j]dp[i][j]={dp[i+1][j+1]+dp[i+1][j],dp[i+1][j],s[i]=t[j]s[i]=t[j]

最终计算得到 dp[0][0]dp[0][0] 即为在 ss 的子序列中 tt 出现的个数。

3.代码实现

```java class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); if (m < n) { return 0; } int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) { dp[i][n] = 1; } for (int i = m - 1; i >= 0; i--) { char sChar = s.charAt(i); for (int j = n - 1; j >= 0; j--) { char tChar = t.charAt(j); if (sChar == tChar) { dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]; } else { dp[i][j] = dp[i + 1][j]; } } } return dp[0][0]; } }
```