# 792. Number of Matching Subsequences

## Description

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 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

## Solutions

• class Solution {
public int numMatchingSubseq(String s, String[] words) {
Deque<int[]>[] d = new Deque[26];
Arrays.setAll(d, k -> new ArrayDeque<>());
for (int i = 0; i < words.length; ++i) {
d[words[i].charAt(0) - 'a'].offer(new int[] {i, 0});
}
int ans = 0;
for (char c : s.toCharArray()) {
var q = d[c - 'a'];
for (int t = q.size(); t > 0; --t) {
var p = q.pollFirst();
int i = p[0], j = p[1] + 1;
if (j == words[i].length()) {
++ans;
} else {
d[words[i].charAt(j) - 'a'].offer(new int[] {i, j});
}
}
}
return ans;
}
}

• class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<queue<pair<int, int>>> d(26);
for (int i = 0; i < words.size(); ++i) d[words[i][0] - 'a'].emplace(i, 0);
int ans = 0;
for (char& c : s) {
auto& q = d[c - 'a'];
for (int t = q.size(); t; --t) {
auto [i, j] = q.front();
q.pop();
if (++j == words[i].size())
++ans;
else
d[words[i][j] - 'a'].emplace(i, j);
}
}
return ans;
}
};

• class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
d = defaultdict(deque)
for i, w in enumerate(words):
d[w[0]].append((i, 0))
ans = 0
for c in s:
for _ in range(len(d[c])):
i, j = d[c].popleft()
j += 1
if j == len(words[i]):
ans += 1
else:
d[words[i][j]].append((i, j))
return ans

• func numMatchingSubseq(s string, words []string) (ans int) {
type pair struct{ i, j int }
d := [26][]pair{}
for i, w := range words {
d[w[0]-'a'] = append(d[w[0]-'a'], pair{i, 0})
}
for _, c := range s {
q := d[c-'a']
d[c-'a'] = nil
for _, p := range q {
i, j := p.i, p.j+1
if j == len(words[i]) {
ans++
} else {
d[words[i][j]-'a'] = append(d[words[i][j]-'a'], pair{i, j})
}
}
}
return
}