---
comments: true
difficulty: Medium
edit_url: https://github.com/doocs/leetcode/edit/main/solution/0700-0799/0792.Number%20of%20Matching%20Subsequences/README_EN.md
tags:
- Trie
- Array
- Hash Table
- String
- Binary Search
- Dynamic Programming
- Sorting
---
<!-- problem:start -->
# [792. Number of Matching Subsequences](https://leetcode.com/problems/number-of-matching-subsequences)
[中文文档](/solution/0700-0799/0792.Number%20of%20Matching%20Subsequences/README.md)
## Description
<!-- description:start -->
<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</code>.</p>
<p>A <strong>subsequence</strong> 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.</p>
<ul>
<li>For example, <code>"ace"</code> is a subsequence of <code>"abcde"</code>.</li>
</ul>
<p> </p>
<p><strong class="example">Example 1:</strong></p>
<pre>
<strong>Input:</strong> s = "abcde", words = ["a","bb","acd","ace"]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: "a", "acd", "ace".
</pre>
<p><strong class="example">Example 2:</strong></p>
<pre>
<strong>Input:</strong> s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
<strong>Output:</strong> 2
</pre>
<p> </p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= s.length <= 5 * 10<sup>4</sup></code></li>
<li><code>1 <= words.length <= 5000</code></li>
<li><code>1 <= words[i].length <= 50</code></li>
<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>
<!-- description:end -->
## Solutions
<!-- solution:start -->
### Solution 1
<!-- tabs:start -->
#### Python3
```python
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
d = defaultdict(deque)
for w in words:
d[w[0]].append(w)
ans = 0
for c in s:
for _ in range(len(d[c])):
t = d[c].popleft()
if len(t) == 1:
ans += 1
else:
d[t[1]].append(t[1:])
return ans
```
#### Java
```java
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Deque<String>[] d = new Deque[26];
Arrays.setAll(d, k -> new ArrayDeque<>());
for (String w : words) {
d[w.charAt(0) - 'a'].add(w);
}
int ans = 0;
for (char c : s.toCharArray()) {
var q = d[c - 'a'];
for (int k = q.size(); k > 0; --k) {
String t = q.pollFirst();
if (t.length() == 1) {
++ans;
} else {
d[t.charAt(1) - 'a'].offer(t.substring(1));
}
}
}
return ans;
}
}
```
#### C++
```cpp
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<queue<string>> d(26);
for (auto& w : words) d[w[0] - 'a'].emplace(w);
int ans = 0;
for (char& c : s) {
auto& q = d[c - 'a'];
for (int k = q.size(); k; --k) {
auto t = q.front();
q.pop();
if (t.size() == 1)
++ans;
else
d[t[1] - 'a'].emplace(t.substr(1));
}
}
return ans;
}
};
```
#### Go
```go
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]string{}
for _, w := range words {
d[w[0]-'a'] = append(d[w[0]-'a'], w)
}
for _, c := range s {
q := d[c-'a']
d[c-'a'] = nil
for _, t := range q {
if len(t) == 1 {
ans++
} else {
d[t[1]-'a'] = append(d[t[1]-'a'], t[1:])
}
}
}
return
}
```
<!-- tabs:end -->
<!-- solution:end -->
<!-- solution:start -->
### Solution 2
<!-- tabs:start -->
#### Python3
```python
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
```
#### Java
```java
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;
}
}
```
#### C++
```cpp
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;
}
};
```
#### Go
```go
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
}
```
<!-- tabs:end -->
<!-- solution:end -->
<!-- solution:start -->
### Solution 3
<!-- tabs:start -->
#### Python3
```python
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
def check(w):
i = -1
for c in w:
j = bisect_right(d[c], i)
if j == len(d[c]):
return False
i = d[c][j]
return True
d = defaultdict(list)
for i, c in enumerate(s):
d[c].append(i)
return sum(check(w) for w in words)
```
#### Java
```java
class Solution {
private List<Integer>[] d = new List[26];
public int numMatchingSubseq(String s, String[] words) {
Arrays.setAll(d, k -> new ArrayList<>());
for (int i = 0; i < s.length(); ++i) {
d[s.charAt(i) - 'a'].add(i);
}
int ans = 0;
for (String w : words) {
if (check(w)) {
++ans;
}
}
return ans;
}
private boolean check(String w) {
int i = -1;
for (int k = 0; k < w.length(); ++k) {
int c = w.charAt(k) - 'a';
int j = search(d[c], i);
if (j == d[c].size()) {
return false;
}
i = d[c].get(j);
}
return true;
}
private int search(List<Integer> t, int x) {
int left = 0, right = t.size();
while (left < right) {
int mid = (left + right) >> 1;
if (t.get(mid) > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
```
#### C++
```cpp
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> d(26);
for (int i = 0; i < s.size(); ++i) d[s[i] - 'a'].emplace_back(i);
int ans = 0;
auto check = [&](string& w) {
int i = -1;
for (char& c : w) {
auto& t = d[c - 'a'];
int j = upper_bound(t.begin(), t.end(), i) - t.begin();
if (j == t.size()) return false;
i = t[j];
}
return true;
};
for (auto& w : words) ans += check(w);
return ans;
}
};
```
#### Go
```go
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]int{}
for i, c := range s {
d[c-'a'] = append(d[c-'a'], i)
}
check := func(w string) bool {
i := -1
for _, c := range w {
t := d[c-'a']
j := sort.SearchInts(t, i+1)
if j == len(t) {
return false
}
i = t[j]
}
return true
}
for _, w := range words {
if check(w) {
ans++
}
}
return
}
```
<!-- tabs:end -->
<!-- solution:end -->
<!-- problem:end -->