判斷子序列

題目描述：給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。

字符串的一個(gè)子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對(duì)位置形成的新字符串。（例如，"ace"是"abcde"的一個(gè)子序列，而"aec"不是）。

進(jìn)階：

如果有大量輸入的 S，稱作 S1, S2, ... , Sk 其中 k >= 10億，你需要依次檢查它們是否為 T 的子序列。在這種情況下，你會(huì)怎樣改變代碼？

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/is-subsequence/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：雙指針遍歷

首先，判斷幾種特殊場(chǎng)景：

• 如果s子串為空，則s一定是t的子序列，直接返回true；

• 如果s不為空，t為空，則s不可能是t的子序列，直接返回false；

• 如果s子串的長(zhǎng)度大于t的長(zhǎng)度，則s不可能是t的子串，直接返回false。

如果不是特殊情況，則使用雙指針?lè)謩e指向s和t的第一個(gè)字符，然后遍歷s和t的字符，遍歷過(guò)程如下：

• 如果s還未遍歷的字符串長(zhǎng)度大于t還未遍歷的字符串長(zhǎng)度，則s不可能是t的子串，直接返回false；

• 如果s和t當(dāng)前位置的字符相同，則指針同時(shí)往后移動(dòng)一位；

• 如果s和t當(dāng)前位置的字符相同，則指向t的指針往后移動(dòng)一位；

• 遍歷結(jié)束的條件就是s或t遍歷到最后一位。

最后，判斷如果s遍歷完成，說(shuō)明s是t的子序列，返回true；否則，返回false。

【每日寄語(yǔ)】 站起來(lái)做人，彎下腰做事。