題目連結:
題目意譯:
給定一字串 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|)))。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。