力扣 392. 判断子序列 dp双指针

https://leetcode-cn.com/problems/is-subsequence/ 思路：有一个显然正确的贪心：对于任意一个字符$i$，假设可选的匹配位置有$po{s}_1、po{s}_2$，且$po{s}_1<po{s}_2$，那么应该选择$po{s}_1$而不是$po{s}_2$。双指针的做法就不说了，说一下后续挑战怎么搞。第一个思路我们用$vec[i][j]$记录字符串$t$中第$j+1$次出现的字符$i$的位置，然后再遍历一次字符串$s$，根据贪心选取最靠前的位置即可。

class Solution { public: bool isSubsequence(string s, string t) { vector<int> vec[26]; int siz=t.size(); for(int i=0;i<siz;i++) vec[t[i]-'a'].push_back(i); bool flag=true; int pos=-1,idx; siz=s.size(); for(int i=0;i<siz&&flag;i++){ idx=upper_bound(vec[s[i]-'a'].begin(),vec[s[i]-'a'].end(),pos)-vec[s[i]-'a'].begin(); if(idx==vec[s[i]-'a'].size()) flag=false; else pos=vec[s[i]-'a'][idx]; } return flag; } };

上面这个思路比较节省空间，但是时间复杂度要比$O(len(s))$高一点，大概要再乘个$log$。我们可以把上面的数组转换一下，用$vec[i][j]$记录从字符串$t$的位置$i$开始，字符$j$出现的第一个位置。这样时间复杂度就可以降到$O(len(s))$了，但是空间复杂度和初始化的时间复杂度较高。

class Solution { public: bool isSubsequence(string s, string t) { int siz=t.size(); vector<vector<int>> vec(siz+1,vector<int>(26)); for(int i=0;i<26;i++) vec[siz][i]=siz; for(int i=siz-1;i>=0;i--){ for(int j=0;j<26;j++){ if(t[i]=='a'+j) vec[i][j]=i; else vec[i][j]=vec[i+1][j]; } } int n=s.size(),idx=0; for(int i=0;i<n;i++){ idx=vec[idx][s[i]-'a']; if(idx==siz) return false; ++idx; } return true; } };