題目連結:
題目意譯:
給定兩字串 s 以及 t,判斷 s 是否為 t 的子序列(Subsequence)。
一個字串中的子序列為:一個新字串,其由原字串在不影響剩下的字元之相對順序的情況下,刪除若干個字元(可以不刪)後所剩下的字元組成。(例,字串 "ace" 是 "abcde" 的一個子序列,而 "aec" 不是)
進階:
如果有很多個 s 之輸入,依序編號為 s1 、 s2 、 …… 、 sk ,其中 k ≧ 10億,而你想要一個一個地檢查是否為 T 的子序列。在這樣的情況下,你會怎麼修改你的程式碼?
限制:
0 ≦ s.length ≦ 100
0 ≦ t.length ≦ 10 ^ 4
兩個字串皆只由小寫字母組成。
範例測資:
範例 1:
輸入: s = "abc", t = "ahbgdc"
輸出: true
範例 2:
輸入: s = "axc", t = "ahbgdc"
輸出: false
解題思維:
掃過 t 的字元,並且用一指標 Ps 代表目前要檢查之 s 中的字元。倘若目前看到的 t 之字元與 Ps 指到的字元式相同的,則將 Ps 指向下一個字元。如果 Ps 已經超出 s 的結尾的話,則跳出掃描 t 字元之迴圈。
做完以上步驟後,判斷 Ps 是否有指到字串 s 的「後面」。如果有則代表 s 中的每個字元都有在 t 中有按照順序的對應(也就是保有相對順序),因此 s 為 t 的子序列;反之,則代表 s 不是 t 的子序列。
進階:
如果有多個 s,則我們可以先將 t 的每個字元與其索引值用一結構(Struct)存在一起。然後將這些結構依照儲存的字元之字典序由小排到大。
此時,因為 t 的所有字元都依字典序排(注意,原本的索引值資訊還有留著),所以當掃過 s 時,每個字元可以用二分搜尋法(Binary Search)去找到符合的字元,並用一個變數紀錄上一個字元對應的索引值,而當前字元的二分搜之結果(也是一個索引值)應大於上一字元的索引值(當然,如果可以大於上一個,則結果應越小越好,不然可能使後面沒得找)。
如果 s 中有字元利用二分搜尋法找不到對應字元,或是所有符合的字元其原本的索引值皆小於等於上一字元找到的索引值,則代表 s 不是 t 的子序列;反之,則是。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。