Count matching words with a subsequence of S

dfa-match-subseq.cpp

// https://leetcode.com/problems/number-of-matching-subsequences/submissions/
class Solution {
public:
    int getCode(char c) {
        return c - 'a';
    }
    
    bool recognized(vector< array<int,26> > const& dfa, string const& w) {
        int cur = 0;
        for (char c : w) {
            if (dfa[cur][getCode(c)] == -1) return false;
            cur = dfa[cur][getCode(c)];
        }
        return true;
    }
    
    auto buildDFA(const string& S) {
        // build DFA
        int N = S.size();
        vector< array<int,26> > dfa(N+1); // DFA
        array<int, 26> next;
        next.fill(-1);
        for (int i = N; i >= 0; --i) {
            dfa[i] = next;
            if (i != 0)
                next[getCode(S[i-1])] = i;
        }
        return dfa;
    }
    
    int numMatchingSubseq(string S, vector<string>& words) {
        auto const& dfa = buildDFA(S);
        // for each word check if it is recognized by DFA
        int res = 0;
        for (const auto& w : words) {
            if (recognized(dfa, w))
                ++res;
        }
        return res;
    }
};