題目地址:

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個用例, 復雜度極高:

能不能優(yōu)化一下呢? 又想到了雙指針, 比dp快了一點過了40多個用例，結果繼續(xù)超時。。。

由于s的數據長度范圍太大了, dp的方法貌似不太好優(yōu)化，那么我們先來優(yōu)化一下雙指針。

我們再看一下子序列的性質:?

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 進行操作, 收集每個字符出現(xiàn)的位置并記錄在一個數組中。容易證明記錄出現(xiàn)位置的這個數組是排好序的(在for循環(huán)作用下單調遞增了)，因此我們可以用二分查找進行優(yōu)化，只要保證二分查找后的位置比當前位置大, 那么該字符串就為s的子序列了: