792. Number of Matching Subsequences

origin

class Solution {
public:
    int numMatchingSubseq (string S, vector<string>& words) {
        int r = 0;
        vector<vector<int>> posMap(26, vector<int>(0));
        for (int i = 0; i < S.length(); i++) {
            posMap[S.at(i) - 'a'].push_back(i);
        }
        int i, j, k;
        for (i = 0; i < words.size(); i++) {
            int pos = -1;
            for (j = 0; j < words[i].length(); j++) {
                char c  = words[i].at(j);
                int idx = c - 'a';
                for (k = 0; k < posMap[idx].size(); k++) {
                    if (posMap[idx][k] > pos) {
                        pos = posMap[idx][k];
                        break;
                    }
                }
                if (k == posMap[idx].size()) {
                    break;
                }
            }
            if (j == words[i].length()) {
                r++;
            }
        }
        return r;
    }
};

improve

class Solution {
public:
    int numMatchingSubseq (string S, vector<string>& words) {
        int r = 0 ;
        vector<vector<int>> posMap(26, vector<int>(0));
        for (int i = 0; i < S.length(); i++) {
            posMap[S.at(i) - 'a'].push_back(i);
        }
        int i, j, k;
        vector<int> current(26, 0);
        for (i = 0; i < words.size(); i++) {
            int pos = -1;
            for (j = 0; j < words[i].length(); j++) {
                char c  = words[i].at(j);
                int idx = c - 'a';
                for (k = current[idx]; k < posMap[idx].size(); k++) {
                    if (posMap[idx][k] > pos) {
                        pos = posMap[idx][k];
                        current[idx] = k + 1;
                        break;
                    }
                }
                if (k == posMap[idx].size()) {
                    break;
                }
            }
            if (j == words[i].length()) {
                r++;
            }
        }
        return r;
    }
};