付費限定文章

判定字串s是否為字串t的子序列_Leetcode 精選75題

Andrew Palmer on Unsplash

題目敘述

題目會給我們兩個輸入，字串s和字串t，要求我們判定s是否為t的子序列(Subsequence)?

題目的原文敘述

測試範例

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

約束條件

Constraints:

• 0 <= s.length <= 100

字串s的長度介於0~100之間，代表字串s有可能是空字串。

• 0 <= t.length <= 10^4

字串t的長度介於0~10^4之間，代表字串t有可能是空字串。

• s and t consist only of lowercase English letters.

字串s和字串t都只會包含小寫英文字母。

演算法

這一題也和前一題字串壓縮類似，使用到雙指針Two pointers的技巧。

idx_s, idx_t 都初始化為0，代表起頭位置。

接著，每次迭代idx_t+1，向右掃描每個字元，同時檢查idx_s所指向的字元。

假如有對應到，就把相對的idx_s也累加1，向右移動。

假如s是t的子序列，那麼代表s內的每個字元都有對應到，最後idx_s應該等於len(s)

程式碼