方法一(双指针)
实现思路
按照判断序列依次遍历,子序列下标从0开始,如果恰好顺次对应到序列中,子序列的下标增1,当子序列完全都匹配时说明包含子序列
概括:从前往后遍历t串,判断s串中的第k个字符是否能匹配到
实现代码
class Solution {
public:
bool isSubsequence(string s, string t) {
int index=0;
if(!s.length()&&!t.length()) return true;
for(int i=0;i<t.length();i++){
if(t[i]==s[index]) index++;
if(index==s.size()) return true;
}
return false;
}
};
提交结果及分析
时间复杂度O(n+m)
遍历的是字符串S和T的长度,所以时间复杂度是O(n+m)
方法二(DP)
实现思路
存储T字符串,第i个位置之后各个字母出现第一次出现的位置(注意计算的时候从后往前)
当匹配成功时,S移动一个字符,T移到的匹配那行的下一行
这种解法的好处在于提前将T中信息存储起来,在遍历T的时候不需要从头开始遍历,这种遍历只需要一种跳跃式的方法
实现代码
//dp解法
bool isSubsequence(string s, string t){
int n = s.length(),m = t.length();
//dp数组dp[i][j]表示字符串t以i位置开始第一次出现字符j的位置
vector<vector<int>> dp(m + 1,vector<int> (26,0));
//初始化边界条件,dp[i][j] = m表示t中不存在字符j
for(int i=0;i<26;i++){
dp[m][i] = m;
}
//从后往前递推初始化dp数组
for(int i = m - 1;i>=0;i--) {
for(int j=0;j<26;j++){
if(t[i] == 'a' + j){
dp[i][j] = i;
}else {
dp[i][j] = dp[i + 1][j];
}
}
}
int add = 0;
for(int i = 0;i<n;i++){
//t中没有s[i] 返回false
if(dp[add][s[i] - 'a'] == m){
return false;
}
//否则直接跳到t中s[i]第一次出现的位置之后一位
add = dp[add][s[i] - 'a'] + 1;
}
return true;
}