基本資料#
難易度: easy 第一次嘗試：2022-08-23
- 提交紀錄：Runtime Error ×2 → Accepted ×2 → Runtime Error → Accepted ×2 → Runtime Error → Wrong Answer → Accepted ×3 → Runtime Error → Wrong Answer → Runtime Error ×2 → Accepted
解題思路#
兩個字串各一個指針（Two Pointers 模板二）：j 掃過 t，t[j] == s[i] 時 i 前進。迴圈條件是 i < len(s) and j < len(t)，最後 i == len(s) 就成立。這樣 s 或 t 是空字串都不用特別處理。進階題有很多個 s 時，先把 t 每個字元出現的位置存起來，對每個 s 用 binary search 找下一個位置。
我的嘗試#
這題寫了很多次（2022、2025、2026），錯誤幾乎都在空字串和邊界：
- 2022-08 用 queue
pop(0)，s是空的時候queue[0]超出範圍。 - 2022-11 寫成
if not t or not s: return False，s是空字串時應該是True：('', '')回傳False。 - 2025 年內層
while t[r] != s[l]在t是空的時直接 IndexError；補上if not t: return False又把('', '')弄錯了；配對後r += 1超出範圍也沒檢查：('bb', 'b')IndexError。 - 2026 年的版本只在不相同時檢查
right == m，t是空字串時第一次比較就超出範圍；把邊界放進while條件才 AC。
正確解法#
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
for c in t:
if i < len(s) and s[i] == c:
i += 1
return i == len(s)
複雜度#
時間 O(n + m)，空間 O(1)。
要特別避免的錯誤#
s是空字串時答案是True，就算t也是空的。- 存取
t[j]之前要確認j沒有超出範圍，包括配對成功、j前進之後。
面試口說整理#
我用兩個指針，掃過 t 的每個字元，跟 s 目前的字元相同就把 s 的指針往前，最後 s 的指針走完就是子序列。時間 O(n + m)、空間 O(1)。