LeetCode 392: Is Subsequence

這題剛看完時當下設計了一個 check 指向 s、一個 run 遍歷 t，感覺邏輯上是對的， 但寫著寫著發現有幾個 edge case 沒考慮進去（s 是空字串會直接掛掉），然後用 AI 整理後才知道其實可以寫得非常簡潔。

題目

題目連結：LeetCode 392. Is Subsequence

給定字串 s 和 t，判斷 s 是否為 t 的子序列（Subsequence）。

子序列的定義：從 t 中刪除若干字元（可以不刪）後，剩下的字元照原本順序排列，能組成 s。

Example 1:

• Input: s = "abc", t = "ahbgdc"
• Output: true（ahbgc ✓）

Example 2:

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

思路

1. 用 check 記錄 s 目前比對到哪個位置（從 0 開始）
2. 遍歷 t 的每個字元，如果等於 s[check]，就把 check 往前推
3. 跑完 t 之後，如果 check == len(s) 代表 s 的每個字元都被依序找到

空字串是任何字串的子序列，check 從 0 開始，len(s) 也是 0，條件會直接通過，因此不需要特判。

走一遍範例

用 s = "abc"、t = "ahbgdc" 走一遍：

Table: 實際走訪過程

check (3) == len(s) (3) → 回傳 true ✓

我的原始寫法

第一版寫出來長這樣：

def isSubsequence(s: str, t: str) -> bool:
    if len(s) > len(t):
        return False
    if len(s) == 1:
        return s in t

    check = 0

    for run in range(len(t)):
        c = s[check]
        if c == t[run]:
            check += 1
        if check >= len(s):
            return True

    return False

方向是對的，但有幾個問題：

1. 沒考慮 s 是空字串，s[check] 在 len(s) == 0 時直接 IndexError
2. len(s) == 1 的特判多餘，主迴圈本來就能處理這個情況
3. 用 range(len(t)) 然後又 t[run]，可以直接用 for char in t 更 Pythonic
4. if check >= len(s): return True 放在迴圈內，雖然提前結束沒問題，但放外面更清楚

最佳解

問了AI之後，把上面的問題修掉，結構就變得很乾淨：

def isSubsequence(s: str, t: str) -> bool:
    check = 0

    for char in t:
        if check < len(s) and s[check] == char:
            check += 1

    return check == len(s)

if check < len(s) 這個 guard 有兩個作用：

1. 防止 s 是空字串時 s[check] 越界
2. s 全部比對完後，後面的字元不會再增加 check（避免多餘的比較）

複雜度

• 時間複雜度：$O(|t|)$。只需遍歷 t 一次，s 的長度不影響迴圈次數。
• 空間複雜度：$O(1)$。只用了 check 一個變數。

小結

這題是 Two Pointers 的入門題型，兩個序列各一個指標「同步推進」。 一開始的多餘特判（len(s) == 1、提前 return）都是因為對主迴圈的邏輯不夠有信心， 只要確定主迴圈能涵蓋所有情況，就能直接刪掉。

空字串是常見的 edge case，Two Pointers 類型的題目，下次第一步應該要先問自己：「其中一個序列長度是 0 時，邏輯還通嗎？」