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 * 1041 <= words.length <= 50001 <= words[i].length <= 50sandwords[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<string>& words) {
int res = 0;
vector < vector<int>>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;
}
};
Input
s = "abcde", words = ["a","bb","acd","ace"]
Output
3
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map();
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 < int[]> values = map.getOrDefault(c, new ArrayList<>());
map.put(c, new ArrayList<>());
for (int[] val : values) {
int stringIdx = val[0];
int wordIdx = val[1];
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;
}
}
Input
s = "abcde", words = ["a","bb","acd","ace"]
Output
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[0]] == null) hash[w[0]] = []
const it = w[Symbol.iterator]()
hash[w[0]].push( it )
it.next()
}
let res = 0
for(let ch of s) {
const advance = hash[ch] || []
hash[ch] = []
for(let it of advance) {
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
};
Input
s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output
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))
Input
s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output
2