392. Is Subsequence

问题：

求给定字符串s 是否为字符串t 的子序列。

Example 1:
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
 
Constraints:
0 <= s.length <= 100
0 <= t.length <= 10^4
s and t consist only of lowercase English letters.

解法：two pointers（双指针）Binary Search（二分查找）

解法一：two pointers（双指针）

两指针 i 和 j ，同时遍历s 和 t。

若当前两字符相同，子序列 s指针i 和全序列 t指针j 同时后移一位+1

否则，只移动全序列 t的指针 j +1。

代码参考：

 1 class Solution {
 2 public:
 3     bool isSubsequence(string s, string t) {
 4         int n=s.length(), m=t.length();
 5         if(n==0) return true;
 6         if(m==0) return false;
 7         int i=0, j=0;
 8         while(i<n && j<m) {
 9             if(s[i]==t[j]) i++;
10             j++;
11         }
12         
13         return i==n;
14     }
15 };

解法二：Binary Search（二分查找）

对全序列 t的所有字母位置进行整理->map

key：字母
value：该字母在t中的index列表。

遍历子序列 s，同时记录当前查找 t 中的位置 j。

对每一个字母：s[i]

若不存在map中的index列表，return false。
若存在map[s[i]]的index列表，找到index>=j的第一个index，
- 该index即为选取子序列该字母在全序列t中的位置。下一个字母从该位置的下一个开始：更新 j=index+1。
- 若未找到满足条件的index（index>map[s[i]].size()）。return false。

代码参考：

 1 class Solution {
 2 public:
 3     bool isSubsequence(string s, string t) {
 4         if(s.length()==0) return true;
 5         if(t.length()==0) return false;
 6         unordered_map<int, vector<int>> mp; // char:idx_list
 7         //make t -> mp
 8         for(int i=0; i<t.length(); i++) {
 9             mp[t[i]].push_back(i);
10         }
11         // traverse s
12         // j: check start idx of t
13         int j=0;
14         for(int i=0; i<s.length(); i++) {
15             if(mp.count(s[i])==0) return false;
16             int idx = distance(mp[s[i]].begin(), 
17                                lower_bound(mp[s[i]].begin(), mp[s[i]].end(), j));
18             if(idx>=mp[s[i]].size()) return false;
19             j = mp[s[i]][idx]+1;
20         }
21         return true;
22     }
23 };