给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:
- 所有在
words和S里的单词都只由小写字母组成。 S的长度在[1, 50000]。words的长度在[1, 5000]。words[i]的长度在[1, 50]。
class Solution:def numMatchingSubseq(self, S, words):""":type S: str:type words: List[str]:rtype: int"""w=collections.defaultdict(list)count=0for i in range(len(S)):#记下来每个字母出现的位置w[S[i]].append(i)for i in range(len(words)):nextCharPos=-1flag2=Truefor j in range(len(words[i])):c=words[i][j]if w[c]==[]:#这个字母在s中存在才有可能是子串flag2=Falsebreakelse:#如果不在，该串不是子串flag=True #是否找到合适的下一个字母for k in range(len(w[c])):if w[c][k]>nextCharPos:nextCharPos=w[c][k]flag=Falsebreakif flag: #如果没找到合适的字母，该串不是子串flag2=Falsebreakif flag2:count=count+1return count