392. Is Subsequence

📘 題目敘述

給定兩個字串 s 與 t，請判斷 s 是否為 t 的子序列（subsequence）。

子序列的定義是：可以從 t 中刪除某些（或不刪除）字元，而不改變剩餘字元的相對順序，若能得到字串 s，則稱 s 是 t 的子序列。

條件限制

0 ≤ s.length ≤ 100
0 ≤ t.length ≤ 10^4
s 與 t 只包含小寫英文字母

🧠 解題思路

我把這題想成一個「依序配對」的問題。

核心概念是：

我不需要連續比對
只要能按照順序在 t 中找到 s 的每一個字元即可

因此我的做法是：

用一個指標 pos 指向目前要比對的 s 的位置
從左到右掃描整個 t
只要 t 中出現的字元剛好等於 s[pos]，就代表這一個字元成功配對，pos++
如果最後能把 s 的所有字元都配對完成，就代表 s 是 t 的子序列

所有變數

s：目標子序列
t：被檢查的原始字串
n1：s 的長度
n2：t 的長度
pos：目前已經成功配對到 s 的第幾個字元（索引）

🪜 主要流程步驟

初始化

設定 pos = 0
表示一開始還沒配對到 s 的任何字元

掃描字串 `t`

我用一個 for 迴圈，從左到右掃描整個 t：

對於每一個 t[i]：

情況一：`t[i] == s[pos]`

代表成功找到 s 的下一個需要的字元
將 pos++，準備比對 s 的下一個字元

情況二：`t[i] != s[pos]`

代表這個字元不是目前需要的
直接跳過，繼續往後找

這樣做的效果是：

永遠保持 s 的字元順序不變
t 只扮演「提供來源」的角色

判斷結果

當整個 t 掃描完後：

如果 pos == n1
- 代表 s 的所有字元都已經依序配對完成
- 回傳 true
否則
- 表示中途配對失敗
- 回傳 false

💡 整體邏輯總結

這題的重點在於：

不需要回頭
不需要刪字元
只要用一個指標記錄「目前匹配到哪裡」

這是一個非常典型的 Two Pointers 題型：

一個指標隱含在 for 迴圈中（掃描 t）
一個指標 pos 用來追蹤 s 的進度

時間複雜度為 O(|t|)，空間複雜度為 O(1)。

💻 程式碼實作

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n1 = s.size();
        int n2 = t.size();
        int pos = 0;
        for (int i = 0; i < n2; i++) {
            if (s[pos] == t[i]) {
                pos++;
            }
        }
        if (pos == n1) {
            return true;
        } else {
            return false;
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/is-subsequence/