当前位置：首页 > news >正文

392. 判断子序列

news 2026/8/23 2:41:12

一.题目描述

二.解题思路

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 = 字符串的长度。这种情况考虑到了就行，别对差了一位。 } }