算法简单题，吾辈重拳出击 - 判断子序列
题目：
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。 进阶： 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false解：
第一反应
把字符串变成数组，循环 s 数组，每一项去 t 数组里面找（find），如果不存在的，就 return false；
var isSubsequence = function(s, t) {
sArr = s.split("")
tArr = t.split("")
let res = true
tArr.map(i=>{
if(!sArr.find(s=>s===i)){res = false}
})
return res
};
解答错误，敲！原来是要按顺序的，这下就麻烦一点了。
第二反应
看一下解析，找一下关键词，噢，双指针，那懂了：
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
if(s==="") return true
let p0 = 0
let p1 = 0
while(p1<t.length){
if(s[p0]===t[p1]){
p0++
}
if(p0===s.length){
return true
}
p1++
}
return false
};思路：设两个指针，初始位置都在字符串的第一位。
当两个指针所指数字相等，说明子字符在父字符中找到了对应的字符，并且是依次找的。此时，父子字符的指针都加一，向右移动。
如果不相等，仅移动父字符串的指针向右加一。
当父字符的指针指向了最后一位，而子字符的指针没有指向最后一位，说明没找到，返回 false；如果在这个过程中子字符就已经遍历完了，说明找到了，返回 true。
双指针！太强了！
（动图来自：Krahets）
第三反应
如果非要用数组呢？
var isSubsequence = function(s, t) {
if(s.length == 0) return true;
let sStack = s.split('');
let tStack = t.split('');
while(tStack.length>0){
let tItem = tStack.pop();
if(tItem == sStack[sStack.length-1]){
sStack.pop();
if(sStack.length == 0) return true;
}
}
return false;
};思路和双指针相似，但具体操作有差异，要用到 pop() 剔除掉找到了的字符。
第四反应
复习一下 while 和 for 的区别：
- for循环是在序列穷尽时停止，while循环是在条件不成立时停止。
- for循环语句申明循环变量，while循环语句判断循环条件。
- 需要在读文本文件中有很多逻辑判断时，采用while比较好。 没有复杂的逻辑判断时用for比较好。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
