前往
大廳
主題

LeetCode - 792. Number of Matching Subsequences 解題心得

Not In My Back Yard | 2021-09-15 00:00:05 | 巴幣 0 | 人氣 231

題目連結:


題目意譯:
給定一字串 s 以及一字串陣列 words ,回傳 words[i] 中為 s 子序列的字串數量。

一個字串的子序列為一個新的字串,其藉由刪除掉原始字串的某些字元(可能沒有)且不更動剩餘字元的相對順序下產生。

例如, "ace" 為 "abcde" 的一個子序列。

限制:
1 ≦ s.length ≦ 5 × 10 ^ 4
1 ≦ words.length ≦ 5000
1 ≦ words[i].length ≦ 50
s 和 words[i] 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: s = "abcde", words = ["a","bb","acd","ace"]
輸出: 3
解釋: words 中有三個字串為 s 的子序列:"a" 、 "acd" 、 "ace" 。

範例 2:
輸入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
輸出: 2


解題思維:
利用這題進階探討中的二分搜尋法(Binary Search)便可以快速地判斷每個 words[i] 是否為 s 的子序列(單一個 words[i] 判斷之時間複雜度為 O(|words[i]| × log(|s|)))。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作