Leetcode 792: Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/description/

Notes:

This question is the same as the follow up question of Leetcode 392.

See the code below:

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        int res = 0;
        vector<vector<int>> ids(26);
        for(int i=0; i<S.size(); ++i) ids[S[i]-'a'].push_back(i);
        for(auto &w : words) {
            if(w.size() > S.size()) continue;
            int id = -1, i = 0;
            for(; i<w.size(); ++i) {
                int t = w[i] - 'a';
                auto it = upper_bound(ids[t].begin(), ids[t].end(), id);
                if(it == ids[t].end()) break;
                id = *it;
            }
            if(i == w.size()) ++res;
        }
        return res;
    }
};