[LeetCode] 792. Number of Matching Subsequences

轉自LeetCode

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

 

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solution

這題應該要是 hard 才對

想法如下

首先，先建立 s 裡面每個 char 有出現在哪些位置上

因為 char 可以重複，所以是用個 list 來存

這時候對每個 word 做檢查，看看是不是 s 的 subsequence

首先，檢查長度，一定要小於等於 s.length

然後 word 裡面的char的前後順序，必須和 s 裡面的 char 一樣

舉例來說 s = "abcab", words = ["aca", "bvb", "aac" ]

map[a] = [0, 3]

map[b] = [1, 4]

map[c] = [2]

當檢查 "aca" 時，拿到 a 在 s 出現的位置是 [0, 3]

因為是初始，先假設目前的 position = -1，用 binary search 找到比 -1 大的值

可以找到 0 這個值，更新 position = 0

把 0 從出現的位置拿掉，因為已經用過了 -> map[a] = [3]

然後接下來是看 c，c 在 s 出現的位置是 [2]

用 binary search 找到比 position = 0 大的值，找到 2

更新 position = 2

把 2 從出現的位置拿掉，因為已經用過了 -> map[c] = []

再看一次a，現在 a 在 s 還有出現的位置只有 [3]

用 binary search 找到比 position = 2 大的值，找到 3

更新 position = 3

這時候，已經把 "aca" 都檢查完了，且都有找到對應的位置

所以 "aca" 可以確認是 s 的一個 subsequence

"bvb" 按照同樣邏輯，只是檢查到 v 時，因為 map 裡面沒有值，所以可以直接結束

"aac"的話，當檢查到 c 的時候， position = 3，但是 c 出現的位置是 [2]，找不到比 3 大的值

所以不是 subsequence

那用 kotlin 實作的時候，注意 map 會需要 copy，因為會重複使用，所以必須保留原始值

kotlin(參考解法)