0392. Is Subsequence (Easy)

Question

Given a string s and a string ** t**, check if ** s** is a subsequence of ** t**.

You may assume that there are only lower case English letters in both s and ** t**. ** t** is potentially a very long (length ~= 500,000) string, and ** s** is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1

s = "abc", ** t** = "ahbgdc"

Return true.

Example 2

s = "axc", ** t** = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

分析/解題

給定一個字串s跟一個字串t，
檢查s是否是t的subsequence(子序列)。可以假設s是一個短字串(長度≤100)且t是一個長字串(長度約500000)。

從原字串t刪除字母(也可以完全不刪)，
並保有原字串的相對位置，所構成的新字串，即為t的子序列。
後面有一個Follow up問的是，
假設這個函式會拿來檢查很多次(k次)不同的S的話(例如會處理1billion次)，
要怎麼實作這個函式比較好？

首先我們先來看看比較直觀的解法。
我們先舉個例子，如果有一個s是”abcde”的話，
s要是t的子序列的條件，就是我們要能在t當中，
依序得到 a~e這五個字母。
那麼第一個我們一定要先找a，假設從t中找到一個a以後，
按照順序的話，這個a以前的bcde就都不能用了 ！
(因為順序就不對啦XD)
同樣的，找到b以後b以前的cde也不能用，以此類推。
因此，我們要保持能確定找到可能性的方式，
就是每一次在t中都取這個順序最前面出現的字母 。

在s當中使用一個記錄index用的i ，
從頭開始找t中的s[i] 在哪，記錄為pre 。
每次找到以後，將i遞增 ，
接下來從t的pre+1處 開始尋找下一個s[i]的位置。
如果找不到的話呢？就表示沒辦法成立，應該回傳false，
否則當全部的s的字母都能找到對應的位置的話，
則代表s可以作為t的子序列。

上面描述這樣的方法，我們使用了兩個索引值，
來記錄s和t當前查找到的位置，
所以這個解法可以視為two pointer手段的一種操作。

同時，我們前面在解的時候，
每次都盡可能 去找最前面出現 的第一個s[i]，
這種概念的想法，僅在特定的題目適用。
當符合在每一個當前狀況都取當前最佳的狀況 ，
全局就會是最佳 的時候，我們就在局部的區段盡可能貪婪。
這樣子的策略被稱為貪婪演算法 (Greedy Algorithm)

請留意到，這種方式往往在很多情況下會失效，
所以在使用前請詳閱公開說明書(X)。
(開玩笑的XD，應該是使用前請確認局部最佳能推導至全局最佳 。)

這麼做基本上要掃過s跟t的字串，所以時間會是O(len(s)+len(t))，
或者說當t遠大於s的時候可以視為O(len(t))。

那麼如果搭配Follow up的條件呢？
如果有k次不同的s的檢查，
就上面的解法而言，每次仍然要各掃過一遍s跟t，
時間複雜度是O(k*(len(s)+len(t))) ，顯然當t很大的時候，
掃過k次是很不理想的，我們會希望能夠化簡一點這個部分。

那要怎麼作呢？這邊引用shuoshankou 在leetcode上的解，
我們可以先針對t建立一個HashMap ，當中的key是t上的字母 ，
而value是這個字母出現在t上面的indices (使用ArrayList來儲存)。
這個儲存過程會是O(len(t)) 。

接著要查找的過程就會變成針對s[i]來搜尋HashMap上的index，
且限定這個index要剛好是在i之後的第一個出現的位置。有沒有覺得很眼熟？沒錯， 這不就是Binary Search嗎？
我們在處理的，就跟對於某個陣列，
搜尋一個值在哪裡(或應插入在哪裡)的問題一樣！

所以就一般來說，搜尋需求是log(N)，
如果前後拆成常數的單位可以忽略不記，
所以對於k個s搜尋所需會是O(k*len(s) * log(len(t))) ，
當k大到一定程度的時候，顯然只作一次O(len(t))先建立對應表，
讓後面的搜尋相關的t的複雜度都變成對數量級 是相當划算的。

注意，以這題的測試資料而言，Binary Search速度並不會跑起來比較漂亮，
原因是測試資料的總數可能相對有限，並不像Follow up假想那樣，
所以前面吃下一整個建立HashMap的時間就會顯得拖累。

Java

Java的部分可以先檢查s和t的長度來避免一些根本不需要跑的狀況，
同時使用indexOf 來搜尋每次的si第一個出現的位置。
(搜尋不到的話indexOf會回傳-1 )

Binary Search的寫法則如註解處，
先建立起HashMap並掃過整個t並依序塞入，
後面再使用getNextIndex來寫Binary Search。
其實如果要能像Follow up那樣反覆利用的話，
應該要能將t的輸入抽離開來，題目的要求和預設寫法並沒有考慮這點，
會導致每次都需要對t建立一個HashMap。

如果要重複利用的話，應該要給定成class Solution的變數，
且建立時能先給入t才對。

Python

Python的部分則使用index 來進行查找，
請留意查找不到的話會產生exception，
所以這邊是使用try/except 來處理的。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(請見上面詳述。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(接下來快要漲成下個價格啦XD)： https://hiskio.com/courses/319?promo_code=VEQZV7E