原题
https://leetcode.cn/problems/is-subsequence/description
解法
最简单的双指针略。
对于进阶场景：如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
需要用kmp的思想提前构建好查询序列。
代码如下
func isSubsequence(s string, t string) bool {
if len(t) == 0{
return len(s) == 0
}
nearestPos := [26]int{}
dp := make([][26]int, len(t) + 1)
for i := len(t) - 1; i >= 0; i--{
temp := nearestPos
dp[i+1] = temp
nearestPos[int(t[i]-'a')] = i+1
}
dp[0] = nearestPos
start := 0
for _, c := range s{
start = dp[start][int(c-'a')]
if start == 0{
return false
}
}
return true
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode392-%e5%88%a4%e6%96%ad%e5%ad%90%e5%ba%8f%e5%88%97/
