@TOC
前言
代码随想录算法训练营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
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。来源：力扣(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 <= s.length, t.length <= 1000
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 到末尾的子字符串。考虑动态规划的边界情况：
当 j=nj=n 时，t[j:]t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意 0≤i≤m0≤i≤m，有 dp[i][n]=1dp[i][n]=1；
当 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
当 s[i]=t[j]s[i]=t[j] 时，dp[i][j]dp[i][j] 由两部分组成：
如果 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]；
如果 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]。
因此当 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]。
当 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]。
因此当 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]; } }
```