题目
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
例如， “ace” 是 “abcde” 的子序列。
示例
示例 1:
输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]
输出: 3
解释: 有三个是 s的子序列的单词: “a”, “acd”, “ace”。
示例 2:
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2
提示:
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。
思路
哈希表+二分查找：
传统的双指针判断是否为子序列的方法在本题会超时，思考一下，这里对字符不匹配的情况做了大量重复判断，所以采用哈希表记录下来
s中出现的字符的所有下标，在遍历words中的某个字符串word时，当我们遍历到word[i]的下一个字符word[i+1]时，我们不需要再依次从s往后匹配，我们只需要找到哈希表中键为word[i+1]，值为大于i的最小值的坐标即为所求坐标（这一步骤可以使用二分查找）。
题解
class Solution: def numMatchingSubseq(self, s: str, words: List[str]) -> int: # 哈希表，存放s中字符与下标的映射 dmap = {} for i, c in enumerate(s): if dmap.get(c): dmap[c].append(i) else: dmap[c] = [i] ans = 0 # 遍历words for w in words: # 判断w中是否所有字符都符合规则 ok = True # 判断的初始最小下标为-1 idx = -1 # 遍历words[i] for i in range(len(w)): idxs = dmap.get(w[i], []) # 二分查找 l, r = 0, len(idxs) - 1 while l < r : mid = l + r >> 1 if dmap.get(w[i], [])[mid] > idx: r = mid else: l = mid + 1 # 未找到符合要求的下标 if r < 0 or dmap.get(w[i], [])[r] <= idx: # 判断条件为False，直接退出 ok = False break # 找到符合要求的下标判断下标需要更改 else: idx = dmap.get(w[i], [])[r] # 若全部字符符合要求则+1，否则不变 ans += 1 if ok else 0 return ans
