leetcode刷题笔记: 792 number-of-matching-subsequences

题目地址:

https://leetcode.cn/problems/number-of-matching-subsequences/

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]

Output: 3

Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

Output: 2

题目大意

给定一个字符串数组words, 输出元素为s的子序列的个数。

首先想到的是dp, 结果只过了21个用例, 复杂度极高:

能不能优化一下呢? 又想到了双指针, 比dp快了一点过了40多个用例，结果继续超时。。。

由于s的数据长度范围太大了, dp的方法貌似不太好优化，那么我们先来优化一下双指针。

我们再看一下子序列的性质: 

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

注意到假如c是s的子序列, 那么 c 的字符一定在 s 中, 这很显然, 并且 c 的字符顺序和 s 是相同的。

我们首先对 s 进行操作, 收集每个字符出现的位置并记录在一个数组中。容易证明记录出现位置的这个数组是排好序的(在for循环作用下单调递增了)，因此我们可以用二分查找进行优化，只要保证二分查找后的位置比当前位置大, 那么该字符串就为s的子序列了: