Description

Submission

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        map<char, vector<int>> mp;

        for(int i = 0; i < s.length(); ++i) {
            mp[s[i]].push_back(i);
        }

        int ret = 0;
        for(auto& word: words) {
            int lower = -1;
            ++ret;
            for(auto ch: word) {
                auto it = upper_bound(mp[ch].begin(), mp[ch].end(), lower);
                if(it == mp[ch].end()) {
                    --ret;
                    break;
                }
                lower = *it;
            }
        }
        return ret;
    }
};

// binary search

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int n = s.length();
        s = "#" + s;
        // vector<vector<int>> states(26, vector<int>(n + 1, -1));
        int states[26][n+1];

        for(int i = 0; i < 26; ++i) {
            states[i][n] = -1;  
        }
        
        for(int i = n - 1; i >= 0; --i) {
            for(int j = 0; j < 26; ++j) {
                states[j][i] = states[j][i+1];
            }
            states[s[i+1]-'a'][i] = i+1;
        }

        int ret = 0;
        for(auto& word: words) {
            int cur = 0;
            ++ret;
            for(auto ch: word) {
                if(states[ch-'a'][cur] == -1) {
                    --ret;
                    break;
                }
                cur = states[ch-'a'][cur];
            }
        }
        return ret;
    }
};

// state machine
//   1 2 3 4 5 6 7 8 9 10
// # a b c d a b a b c d

// state[i][c]: at position i, the next index for c, if none, the value should be -1
// state[10][a] = -1
// state[10][b] = -1
// state[10][c] = -1
// state[10][d] = -1
// make a copy, and replace the info for the next position
// state[10][a] = -1
// state[10][b] = -1
// state[10][c] = 10
// state[10][d] = -1