1-1：题目大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力。
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 100 0 <= t.length <= 104 s and t consist only of lowercase English letters.
Follow up: Suppose there are lots of incoming s, say s1, s2, …, sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-subsequence
这里先写出我自己的思路，我自己的思路和别人都不太一样，最终也AC了（测试用例一共10几个），我也用的dp做。
- s是不是t的子序列，这边首先先注意s的长度如果大于t，就不用做啦，肯定就不是的。
- dp状态：根据以前题目的经验（比如T1143，T718），我们这边用i作为s的遍历索引，j作为t的遍历索引，并且有如下二维dp状态：dp[i][j]代表以s.charAt(i)结尾的序列s[0:i]是否是以t.charAt(j)的序列s[0:j]的子序列。
- 状态转移方程：
(1)当s.charAt(i) == t.charAt(j)，只要子问题s[0:i-1]是t[0:j-1]的子序列，加上s.charAt(i)，t.charAt(j)，s[0:i] 也是 t[0:j]的子序列。这个很好理解，比如s=ac,t=adc；i=1,j=2,s.charAt(i)=c,t.charAt(j)=c，a是ad的子序列，那么加上c，ac也是adc的子序列。
(2)当s.charAt(i) ！= t.charAt(j)，比如s=ac,t=ace，i=1，j=2，c不等于e，只要看[0:i]和[0:j-1]的关系，如果是true，那么即使多一个e,ac依旧是ace的子序列。 - 初始化，处理边界：由于这边是boolean数组，我们需要对第一行进行初始化。单靠dp状态转移方程是做不到的（或者说，我么做= =，尴尬！我菜啊！）。具体怎么初始化，大概是从相等的开始后面都是true,这边a==a,那么a一定是ab，abc，abcd。。的子序列，没啥问题。蓝色的X代表什么意思呢？这里就是s的子序列比t的子序列长的时候，根本不用考虑，因为s的子序列一定是比t短或者相等的。从红线开始计算即可。
public static boolean isSubsequence(String s, String t) {
int n = s.length();
int m = t.length();
if (n == 0) {
return true;
}
if (m == 0 || n > m) {
return false;
}
boolean[][] dp = new boolean[n][m];
char c = s.charAt(0);
for (int i = 0; i < m; i++) {
if (t.charAt(i) == c) {
for (int j = i; j < m; j++) {
dp[0][j] = true;
}
break;
}
}
for (int i = 1; i < n; i++) {
for (int j = i; j < m; j++) {
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
System.out.println(Arrays.deepToString(dp));
return dp[n - 1][m - 1];
}
这边dp数组有效范围是从0开始的，其实从1开始更简单（初始化的时候简单），代码如下，附带列表：
public static boolean isSubsequence3(String s, String t) {
int n = s.length();
int m = t.length();
if (n == 0) {
return true;
}
if (m == 0 || n > m) {
return false;
}
boolean[][] dp = new boolean[n + 1][m + 1];
for (int i = 0; i <= m; i++) {
dp[0][i] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
System.out.println(Arrays.deepToString(dp));
return dp[n][m];
}
a b c d e
[true, true, true, true, true, true],
a[false, true, true, true, true, true],
c[false, false, false, true, true, true],
e[false, false, false, false, false, true]
1-4：答案的idea
答案的idea 是从之前的一道最长公共子序列 1143题 https://blog.csdn.net/qq_41376740/article/details/121248624，得出的，只要公共最长子序列的长度刚好等于s的长度，也就可以得到s是t的子序列。思路可以看我之前的1143题解
1-5：代码public static boolean isSubsequence2(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m] == n;
}
1-6：总结：
这道题也是自己AC出来的，不过我的思路还挺独特的，和别人不一样，也可能测试用例多了就不会通过了，答案的思路还是有点技巧的要想到这么做我觉得不容易，哈哈哈。河海哥的dp越来越有感觉啦！加油吖！如有错误还请纠正，写的还行点个！感谢支持！一起加油！河海哥冲啊！
