AlgoPressAppearance
0392-判断子序列
https://leetcode.cn/problems/is-subsequence
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶： 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？ 致谢： 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
基本思路【ME】
判断 s 是否是 t 的子串，首先判断 s 的第sIndex = 0个字符在 t 中是否存在，如果存在则由 tIndex. 继续判断 s 剩下的字符串s[sIndex+1]到结尾 是否是 t[tIndex+1] 到结尾的子串，递归判断。
当 sIndex 先到达末尾，则判断结束， 返回 true，当 tIndex 先到达结尾说明有字符没有匹配到，返回 false
参考代码
csharp
public class Solution {
private bool IsSub(string s, string t, int sIndex, int tIndex){
if(sIndex >= s.Length){
return true;
}
if(tIndex >= t.Length){
return false;
}
bool found = false;
int foundIndex = 0;
//Console.WriteLine("Enter loop sIndex {0} tIndex {1}", sIndex, tIndex);
for(int i=tIndex; i<t.Length; i++){
if(s[sIndex] == t[i]){
found = true;
foundIndex = i;
//Console.WriteLine("found {0} foundIndex {1}",found, foundIndex);
break;
}
}
found = found && IsSub(s,t,sIndex+1,foundIndex+1);
return found;
}
public bool IsSubsequence(string s, string t) {
return IsSub(s,t,0,0);
}
}
思路2：双指针【对思路1进行简化】
csharp
public class Solution {
public bool IsSubsequence(string s, string t) {
int sIndex = 0;
int tIndex = 0;
while(sIndex < s.Length && tIndex < t.Length){
if(s[sIndex] == t[tIndex]){
sIndex++;
}
tIndex++;
}
//如果都s进行到结尾了，说明找到匹配字符串
return sIndex == s.Length;
}
}
思路3：动态规划
定义 dp[i,j] 表示 s 前 i 个字符，和 t 前 j 个字符 ，是否构成i是j的子序列。 注意包含关系的状态转移
csharp
public class Solution{
public bool IsSubsequence(string s, string t){
int m = s.Length;
int n = t.Length;
//动态规划 dp[i,j] 表示 s中前i个字符和t中前j个字符是否构成子序列关系
bool[,] dp = new bool[m+1,n+1];
//初始化，i为0都是包含于j的
for(int j=0;j<=n;j++){
dp[0,j] = true;
}
//状态转移
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s[i-1] == t[j-1]){
dp[i,j] = dp[i-1,j-1];
}
else{
//如果不相等，如果不包含j是子序列的话，那么本次也是子序列
dp[i,j] = dp[i,j-1];
}
}
}
return dp[m,n];
}
}
复习双指针:20220515
csharp
public class Solution {
public bool IsSubsequence(string s, string t) {
if(s.Length == 0){
return true;
}
int index=0; // source 串索引
for(int i=0; i<t.Length; i++){
if(s[index] == t[i]){
index++;
}
if(index == s.Length){
return true;
}
}
return false;
}
}
复习动规：20220515
注意初始化dp[0,j] 的都是 true，不只是dp[0,0]
csharp
public class Solution {
public bool IsSubsequence(string s, string t) {
if(s.Length == 0){
return true;
}
int m = s.Length;
int n = t.Length;
bool[,] dp = new bool[m+1,n+1];
for(int j=0; j<=n; j++){
dp[0,j] = true; //都是空是符合子序列的
}
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(s[i-1] == t[j-1]){
dp[i,j] = dp[i-1,j-1];
}
else{
dp[i,j] = dp[i,j-1];
}
}
}
return dp[m,n];
}
}