392. Is Subsequence

题目描述

要通过这道题很容易，双指针法即可解决。进阶的问题很有意思。

class Solution {
public:bool isSubsequence(string s, string t) {int len_s = s.size();int len_t = t.size();int j = 0;for(int i = 0;j < len_s && i < len_t;i++){if(s[j] == t[i]){j++;}}return j==len_s;}
};

如果对大量的s字符串都按照上面的方法处理，显然是低效的。在t中查找下一个字符的操作耗费大量时间，每个新的s都要做这个重复的工作，这个事情本身只和t字符串自身的性质以及字符集有关，和s字符串无关。可以对t预处理，求出下一个字符的位置，每次只需要查询这个表即可。

具体看代码：

class Solution {
public:bool isSubsequence(string s, string t) {int len_t = t.size();//dp[i][j],0<=i<=len_t,0=<j<=25//dp[i][j]表示字符串t中从位置i开始往后字符j第一次出现的位置//如果dp[i][j]==len_t表示t中从位置i开始往后不存在字符j,因为t没有位置len_tvector<vector<int>> dp(len_t+1,vector<int>(26,len_t));//初始化只需要将dp[len_t][j] 0<=j<26 全部初始化为len_t就可以,表示字符串t末尾的后面没有字符//其他初始状态可以为任何值，可以不初始化//由于前面定义dp的时候已经把整个dp数组初始化为len_t,所以下面这两行可以省略// for(int j =0;j <26;j++)//     dp[len_t][j] = len_t;for(int i = len_t-1;i >=0;i--){//i必须从大到小遍历// for(int j = 0;j <26;j++){//j从大到小或者从小到大遍历都可以for(int j = 25;j>=0;j--){  //j从大到小或者从小到大遍历都可以if(t[i]-'a' == j){dp[i][j] = i;}else{dp[i][j] = dp[i+1][j];}}}int len_s = s.size();int i = 0;for(int k = 0;k < len_s;k++){if(dp[i][ s[k]-'a' ] == len_t)return false;else{i = dp[i][ s[k]-'a' ];i++;}}return true;}
};