题目地址：https://leetcode.com/problems/number-of-matching-subsequences/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:
1、 AllwordsinwordsandSwillonlyconsistsoflowercaseletters.；
2、 ThelengthofSwillbeintherangeof[1,50000].；
3、 Thelengthofwordswillbeintherangeof[1,5000].；
4、 Thelengthofwords[i]willbeintherangeof[1,50].；
题目大意
找出words里面有多少个S的子序列。注意，子序列可以不连续。
解题方法
最开始想的肯定是DP了，但是这种思路想歪了，因为不同words之间好像没有什么转移方程。。
现在又学到了一个新的判断是不是子序列的方法，使用字典保存s中字母所有索引，然后遍历word寻找索引。
对于word的每个位置的字符，同时用个prev变量保存遍历S时已经到达哪个位置了，然后从字典中寻找这个字符是否存在prev 后面出现过。很巧妙。
时间复杂度是O(S) + O(WLlog(S))，空间复杂度是O(S).
代码如下：
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)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
参考资料：
https://www.youtube.com/watch?v=l8_vcmjQA4g
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发