392. 判断子序列

目录一.题目描述二.解题思路1. 核心思路为什么是贪心2. 状态定义与变量滚动三.代码四.重点一.题目描述给定字符串s和t判断s是否为t的子序列。字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。示例 1输入s abc, t ahbgdc输出true示例 2输入s axc, t ahbgdc输出false提示0 s.length 1000 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 i0; int j0; //3.开始进行贪心算法 //以此拿s的每个字符去匹配t的最左侧这就体现了贪心思想相同的字符这样使得结果为true的可能性最大 while(im-1 jn-1){ //如果字符匹配s的指针向右移动一位 if(s.charAt(i) t.charAt(j)){ i; } //t的指针始终移动 j; } return im;//注意此处的逻辑比如s的长度为3下标最大到2匹配的最后一轮正好i为2但是又执行了一个i因此最后指针会超出最大下标2即到达3的位置。说白了就是 最大下标1 字符串的长度。这种情况考虑到了就行别对差了一位。 } }运行效果四.重点理解本题的核心贪心思想如下对于 s 中的每一个字符我们都在 t 中寻找当前能匹配到的最早出现的位置。一旦匹配成功指针向前移动继续找下一个字符。这句话理解了这题就做出来一大半了。以上就是本篇文章的全部内容喜欢的话可以留个免费的关注呦~~~