Leetcode 392: Is Subsequence

https://leetcode.com/problems/is-subsequence/description/

Notes:

This question is an easy question. Using the so-called two-pointer method. The key is the follow-up question.

See the code below:

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

Now let's look at the follow-up: now there are Billions of s. So we need to find a faster way than the above. One method is group and then binary search: group the index of the same kind of letter in t from small to high; then do a binary search to each letter in s. Or pre-processing t + binary search of s in t

See the code below:

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> ids(26);//in the design, we can set ids as a private attribute
                                    //and can be initialized when instantiating one object
                                    //then call the
        for(int i=0; i<t.size(); ++i) {
            ids[t[i]-'a'].push_back(i);
        }
        int idx = -1;
        for(int i=0; i<s.size(); ++i) {
            int j = s[i] - 'a';
            auto it = upper_bound(ids[j].begin(), ids[j].end(), idx);//the first bigger than idx
            if(it == ids[j].end()) return false;
            idx = *it;
        }
        return true;
    }
};