##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/792.html

# 792. Number of Matching Subsequences

Medium

## Description

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example:

Input:

S = “abcde”

words = [“a”, “bb”, “acd”, “ace”]

Output: 3

Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

## Solution

One solution is to check whether each word in words is a subsequence of S, and count the number of subsequences, which is quite time-consuming since S is looped over many times.

A better solution is to maintain buckets for each letter. For each word in words, for each letter, store the following letters in the buckets. If the end of word is reached, add the counter by 1.

• class Solution {
public int numMatchingSubseq(String S, String[] words) {
int count = 0;
for (int i = 0; i < 26; i++)
for (String word : words)
char[] array = S.toCharArray();
for (char c : array) {
ArrayList<Node> oldBucket = heads[c - 'a'];
heads[c - 'a'] = new ArrayList<Node>();
for (Node node : oldBucket) {
node.index++;
int wordLength = node.word.length();
if (node.index == wordLength)
count++;
else
}
oldBucket.clear();
}
return count;
}
}

class Node {
String word;
int index;

public Node(String word, int index) {
this.word = word;
this.index = index;
}
}

• // OJ: https://leetcode.com/problems/number-of-matching-subsequences/
// Time: O(S + NWlogS)
// Space: O(S)
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& A) {
vector<int> index[26];
for (int i = 0; i < s.size(); ++i) index[s[i] - 'a'].push_back(i);
int ans = 0;
for (auto &w : A) {
int i = 0, j = 0;
for (; i < w.size(); ++i) {
auto &v = index[w[i] - 'a'];
auto it = lower_bound(begin(v), end(v), j);
if (it == end(v)) break;
j = *it + 1;
}
ans += i == w.size();
}
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

############

class Solution(object):
def numMatchingSubseq(self, S, words):
"""
:type S: str
:type words: List[str]
:rtype: int
"""
m = dict()
def isMatch(word, d):
if word in m:
return m[word]
prev = -1
for w in word:
i = bisect.bisect_left(d[w], prev + 1)
if i == len(d[w]):
return 0
prev = d[w][i]
m[word] = 1
return 1

d = collections.defaultdict(list)
for i, s in enumerate(S):
d[s].append(i)
ans = [isMatch(word, d) for word in words]
return sum(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
}