[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(參考解法)

	class Solution {
	fun numMatchingSubseq(s: String, words: Array<String>): Int {
	val map = mutableMapOf<Char, MutableList<Int>>()
	for(i in s.indices) {
	if(map[s[i]] == null) {
	map[s[i]] = mutableListOf<Int>(i)
	} else {
	map[s[i]]!!.add(i)
	}
	}
	var ans = 0
	for(w in words) {
	if(w.length > s.length) {
	continue
	}
	var index = 0
	var currentPos = -1
	val checkMap = mutableMapOf<Char, MutableList<Int>>()
	for(m in map) {
	checkMap[m.key] = m.value.toMutableList()
	}
	while(index < w.length) {
	if(checkMap[w[index]] == null) {
	break
	}
	val indices = checkMap[w[index]]!!
	var left = 0
	var right = indices.size
	while(left < right) {
	val mid = left + (right - left) / 2
	if(indices[mid] < currentPos) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	if (right >= indices.size) {
	break
	} else {
	currentPos = indices[right]
	indices.removeAt(right)
	++index
	}
	}
	if(index == w.length) {
	++ans
	}
	}
	return ans
	}
	}

view raw number_of_matching_subsequences.kt hosted with ❤ by GitHub