392 Is Subsequence

直接將兩個index從頭掃到尾, 當有遇到再把A的index加加就行了, 看最後結束i是否如期走到尾

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

第二個方式算是使用撇步, 不算真的練習到binary search, 不過upper_bound是用binary_search去做的

// Eg-1. s="abc", t="bahbgdca"
    // idx=[a={1,7}, b={0,3}, c={6}]
    //  i=0 ('a'): prev=1
    //  i=1 ('b'): prev=3
    //  i=2 ('c'): prev=6 (return true)
    // Eg-2. s="abc", t="bahgdcb"
    // idx=[a={1}, b={0,6}, c={5}]
    //  i=0 ('a'): prev=1
    //  i=1 ('b'): prev=6
    //  i=2 ('c'): prev=? (return false)

我們先將t的所有可能字母, 將他們的index存起來

最後再掃一次s的元素, 利用upper bound找到大於prev的最小值

並令此作prev, 給下個char使用

class Solution {
public:
    bool isSubsequence(string s, string t) {
        unordered_map<char, vector<int>> m ;
        for(int i = 0; i < t.size();i++){
            char c = t[i];
            m[c].push_back(i);
        }
        int prev = -1;
        for(auto c: s){
            if(!m.count(c)) return false;
            auto it = upper_bound(m[c].begin(), m[c].end(), prev);
            if(it != m[c].end()){
                prev = *it;
            }else{
                return false;
            }
        }
        return true;
    }
};