目录
一.题目描述
二.解题思路
1. 核心思路：为什么是贪心？
2. 状态定义与变量滚动
三.代码
四.重点
一.题目描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
- 两个字符串都只由小写字符组成。
二.解题思路
先声明：这道题可以用动态规划，但是比较复杂，而且杀鸡用不上牛刀。
最高效的算法是“贪心算法”。
解题核心思想如下：
1. 核心思路：为什么是贪心？
直觉思考（抓手）： 假设你要在字符串 t 中找 s 的第一个字符 s[0] 。
- t 中有好几个 'a'，你应该选哪一个？
- 策略：选最靠前的那个。
- 原因：选得越靠前，留给后面字符 s[1], s[2]… 的空间（剩余的 t 的子串）就越大，匹配成功的概率就越高。选后面的 'a' 只会让剩余空间变小，没有任何好处。
结论： 对于 s 中的每一个字符，我们都在 t 中寻找当前能匹配到的最早出现的位置。一旦匹配成功，指针向前移动，继续找下一个字符。
2. 状态定义与变量滚动
既然不需要记录所有历史状态，我们只需要记录“当前匹配到哪儿了”。
我们需要两个变量（指针）：
- i：指向字符串 s 的当前待匹配字符（表示 s 的前 i 个字符已经匹配成功）。
- j：指向字符串 t 的当前扫描位置。
三.代码
将上述的解题思想，转换成如下代码即可（我们用手判断都能判断出来这道题，更别说上代码了，要自信）：
class Solution {
public boolean isSubsequence(String s, String t) {
//声明：这道题用“贪心算法”更加高效
//1.先求出字符串s、t的长度
int m = s.length();
int n = t.length();
//2.再定义两个指针，用于记录遍历s、t过程的下标位置
int i=0;
int j=0;
//3.开始进行贪心算法：
//以此拿s的每个字符，去匹配t的最左侧（这就体现了贪心思想）相同的字符，这样使得结果为true的可能性最大
while(i<=m-1 && j<=n-1){
//如果字符匹配，s的指针向右移动一位
if(s.charAt(i) == t.charAt(j)){
i++;
}
//t的指针始终移动
j++;
}
return i==m;//注意此处的逻辑，比如s的长度为3（下标最大到2），匹配的最后一轮，正好i为2，但是又执行了一个i++，因此最后指针会超出最大下标2，即到达3的位置。说白了就是 最大下标+1 = 字符串的长度。这种情况考虑到了就行，别对差了一位。
}
}
运行效果
四.重点
理解本题的核心贪心思想，如下：
对于 s 中的每一个字符，我们都在 t 中寻找当前能匹配到的最早出现的位置。一旦匹配成功，指针向前移动，继续找下一个字符。
这句话理解了，这题就做出来一大半了。
以上就是本篇文章的全部内容，喜欢的话可以留个免费的关注呦~~~
