792. Number of Matching Subsequences

Problem

Tags: Hash Table, String, Trie, Sorting

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

Constraints:

• 1 <= s.length <= 5 * 10^4
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Code

CPP

// 792. Number of Matching Subsequences (10/18/53444)
// Runtime: 132 ms (94.03%) Memory: 46.04 MB (71.13%) 

class Solution {
public:
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<pair<int, int>> all[128];
        int res = 0, n = words.size();
        for (int i = 0; i < n; i++) {
            all[words[i][0]].emplace_back(i, 1);
        }
        for (char c : S) {
            auto vect = all[c];
            all[c].clear();
            for (auto it : vect) {
                if (it.second == words[it.first].size()) ++res;
                else all[words[it.first][it.second++]].push_back(it);
            }
        }
        return res;
    }
};