給定兩個字串
s和t，判斷s是否是t的子序列。子序列是從原字串中刪除若干（或零個）字元後，不改變剩餘字元相對順序所形成的新字串。
Example:
Input: s = “abc”, t = “ahbgdc” Output: true
Intuition
TIP
核心思路：雙指標，一個掃 s、一個掃 t，在 t 中依序找到 s 的每個字元即可。
- 子序列要求保持相對順序，所以可以貪心地在
t中由左到右匹配s的字元 - 如果
s的指標走完了，代表所有字元都匹配成功
Approaches
1. Brute Force (recursive) — O(n) / O(n)
- Idea: 遞迴檢查，每次嘗試匹配
s[i]和t[j] - Time:
O(n)- n 為t的長度 - Space:
O(n)- 遞迴呼叫堆疊
class Solution {
fun isSubsequence(s: String, t: String): Boolean {
return helper(s, t, 0, 0)
}
private fun helper(s: String, t: String, i: Int, j: Int): Boolean {
if (i == s.length) return true
if (j == t.length) return false
return if (s[i] == t[j]) {
helper(s, t, i + 1, j + 1)
} else {
helper(s, t, i, j + 1)
}
}
}⭐ 2. Two Pointers — O(n) / O(1)
- Idea: 用兩個指標分別指向
s和t，匹配則同時前進，不匹配則只移動t的指標 - Time:
O(n)- n 為t的長度 - Space:
O(1)- 只用兩個指標
class Solution {
fun isSubsequence(s: String, t: String): Boolean {
var i = 0
var j = 0
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
i++
}
j++
}
return i == s.length
}
}Note: Follow-up Preprocessing for Many Queries
如果有大量 s 需要檢查是否為同一個 t 的子序列，可以預處理 t，建立每個字元下一次出現位置的查找表，用二分搜尋加速。
class Solution {
fun isSubsequence(s: String, t: String): Boolean {
// 預處理：記錄 t 中每個字元出現的所有索引
val indexMap = HashMap<Char, MutableList<Int>>()
for ((i, c) in t.withIndex()) {
indexMap.getOrPut(c) { mutableListOf() }.add(i)
}
var prev = -1
for (c in s) {
val indices = indexMap[c] ?: return false
// 二分搜尋找到第一個 > prev 的索引
val pos = indices.binarySearch(prev + 1).let {
if (it >= 0) it else -(it + 1)
}
if (pos >= indices.size) return false
prev = indices[pos]
}
return true
}
}🔑 Takeaways
- Pattern: 雙指標掃描是子序列判斷的標準做法
- Key trick: 子序列 vs 子字串——子序列不要求連續，只要求相對順序；Follow-up 預處理 + 二分搜尋可處理多次查詢