392判断子序列

1 思路：依次取s中元素在t中查找
2 字符串s是字符串t的子序列，那么字符串s中的所有字符都会按照顺序出现在字符串t中。
3 对子串进行遍历，同时也对母串进行遍历，一旦两个字符串匹配之后，就选择从母串匹配后的下一个位置继续下面的匹配，
4 而不在从头开始匹配。空串也是母串的子串。

 1 解法1：
 2 //40 ms    16.8 MB    
 3 class Solution {
 4 public:
 5     bool isSubsequence(string s, string t) {
 6         //暴力的解法
 7         //为空串时 也是子串
 8         int cnt=0;
 9         bool flag;
10         for(int i=0;i<s.size();i++){
11             flag=false;//标记不能找到
12             for(int j=cnt;j<t.size();j++){
13                 if(s[i]==t[j]){
14                     flag=true;//标记能找到
15                     cnt=j+1;//从匹配的字符后面下一个开始 继续查找，当长度10亿时，超时
16                     break;
17                 }
18             }
19             if(flag==false){//没有匹配的单词，可以返回false 了
20                 return false;
21             }
22         }
23          return true;
24     }
25 };

 1 解法2：
 2 //48ms 17 MB
 3 class Solution {
 4 public:
 5     bool isSubsequence(string s, string t) {
 6         //双指针解法：
 7         int i,j;
 8         for(i=0,j=0;i<s.size()&&j<t.size();j++){
 9             if(s[i]==t[j]){
10                 i++;
11             }
12         }
13         return i==s.size();
14 
15     }

16 };

 1  1 思路：
 2  2 
 3  3 状态：dp[i][j]为s的从头开始到i的子字符串是否为t从头开始到j的子字符串的子序列
 4  4 
 5  5 状态转移公式：
 6  6 
 7  7 当char[i]==char[j]时，则字符i一定是j的子序列，如果0~i-1子字符串是0~j-1子字符串的子序列，则dp[i][j]=true，所以dp[i][j] = dp[i-1][j-1]；
 8  8 当char[i]!=char[j]时，即判断当前0~i子字符串是否是0~j-1的子字符串的子序列，即dp[i][j] = dp[i][j - 1]。如ab，eabc，虽然s的最后一个字符和t中最后一个字符不相等，但是因为ab是eab的子序列，所以ab也是eabc的子序列
 9  9 初始化：空字符串一定是t的子字符串的子序列，所以dp[0][j]=true;任意字符串非空 都不是 空字符的字符串 dp[i>0][0]=false;
10 10 
11 11 结果：返回dp[sLen][tLen]
12 
13 解法3：1508 ms    78.3 MB
14 
15 class Solution {
16 public:
17     bool isSubsequence(string s, string t) {
18         //使用动态规划做：虽然很慢，但是需要练习一下
19         int lens=s.size(),lent=t.size();
20         if(lens==0) return true;
21         if(lens>lent) return false;
22       //  bool dp[101][600010];//数组越界初始化500001,遇到551742长度
23         bool dp[lens+1][lent+1];//可以使用 字符串长度进行初始化
24         for(int i=1;i<=lens;i++) dp[i][0]=false;//任意字符串s都不是空串的字符串
25         for(int j=0;j<=lent;j++) dp[0][j]=true;//任意空串 s  都是 字符串t的 子串
26         for(int i=1;i<=lens;i++){
27             for(int j=1;j<=lent;j++){
28                 if(s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1];
29                 else dp[i][j]=dp[i][j-1];
30             }
31         }
32         return dp[lens][lent];
33 
34     }
35 };

 1 解法6：112 ms    34 MB
 2 class Solution {
 3 public:
 4     bool isSubsequence(string s, string t) {
 5         unordered_map<char,vector<int>> mp;
 6         int len,left,right;
 7         for(int i=0;i<t.size();i++){
 8             mp[t[i]].push_back(i);//对每个t中的字符 存储它所在的位置，由小到大
 9         }
10         int curloc=0;//当前位置为0
11         for(char ch:s){//对字符串s中的每个字符 进行遍历
12             len=mp[ch].size();//取出t中相对应字母所在的 所有位置,进行查找
13             if(len==0) return false;//为空,字符串t中没有出现相应的字母 
14             if(curloc>mp[ch][len-1]) return false;//如果当前位置超过t中相对应字符的最后一个位置，无法匹配
15             left=0,right=len-1;
16             while(left<right){//执行完这个二分查找之后，left==right 
17                 int mid=(left+right)/2;
18                 if(mp[ch][mid]>curloc) right=mid;
19                 else left=mid+1;
20             }
21             curloc=mp[ch][left];
22         }
23         return true;
24     }
25 };