# 【LeetCode】792. Number of Matching Subsequences 解题报告（Python）

# 题目描述：

Given string S and a dictionary of words `word`s, 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:

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

# 解题方法

``````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)
``````