## Algorithm

Problem Name: 792. Number of Matching Subsequences

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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int numMatchingSubseq(string S, vector& words) {
int res = 0;
vector>bucket(26);
for(int i = 0; i < S.size(); i++) bucket[S[i] - 'a'].push_back(i);
for(auto s: words){
int pre = -1, cur = -1, i = 0;
for(;i < s.size(); i++){
for(auto x: bucket[s[i] - 'a']){
if(x > pre){
cur = x;
break;
}
}
if(cur == pre) break;
pre = cur;
}
if(i == s.size()) res++;
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "abcde", words = ["a","bb","acd","ace"]

Output

cmd
3

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
map.computeIfAbsent(words[i].charAt(0), k -> new ArrayList<>()).add(new int[]{0, i});
}
int result = 0;
for (char c : s.toCharArray()) {
List values = map.getOrDefault(c, new ArrayList<>());
map.put(c, new ArrayList<>());
for (int[] val : values) {
int stringIdx = val;
int wordIdx = val;
if (stringIdx + 1 == words[wordIdx].length()) {
result++;
} else {
char nextChar = words[wordIdx].charAt(stringIdx + 1);
map.computeIfAbsent(nextChar, k -> new ArrayList<>()).add(new int[]{stringIdx + 1, wordIdx});
}
}
}
return result;
}
}
``````
Copy The Code &

Input

cmd
s = "abcde", words = ["a","bb","acd","ace"]

Output

cmd
3

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numMatchingSubseq = function(s, words) {
const hash = {}
for(let w of words) {
if(hash[w] == null) hash[w] = []
const it = w[Symbol.iterator]()
hash[w].push( it )
it.next()
}
let res = 0
for(let ch of s) {
const advance = hash[ch] || []
hash[ch] = []
const obj = it.next()
if(obj.done === false) {
if(hash[obj.value] == null) hash[obj.value] = []
hash[obj.value].push(it)
} else {
res++
}
}
}

return res
};
``````
Copy The Code &

Input

cmd
s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

Output

cmd
2

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numMatchingSubseq(self, S, words):
def check(s, i):
for c in s:
i = S.find(c, i) + 1
if not i: return False
return True
return sum((check(word, 0) for word in words))
``````
Copy The Code &

Input

cmd
s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

Output

cmd
2