392. Is Subsequence

Easy

Description

給定兩個字串 s 和 t，判斷 s 是否是 t 的子序列。子序列是從原字串中刪除若干（或零個）字元後，不改變剩餘字元相對順序所形成的新字串。

Example:

Input: s = “abc”, t = “ahbgdc” Output: true

Intuition#

核心思路：雙指標，一個掃 s、一個掃 t，在 t 中依序找到 s 的每個字元即可。

子序列要求保持相對順序，所以可以貪心地在 t 中由左到右匹配 s 的字元
如果 s 的指標走完了，代表所有字元都匹配成功

Approaches#

1: Brute Force（遞迴）#

概念: 遞迴檢查，每次嘗試匹配 s[i] 和 t[j]
時間複雜度: O(n) - n 為 t 的長度
空間複雜度: 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#

概念: 用兩個指標分別指向 s 和 t，匹配則同時前進，不匹配則只移動 t 的指標
時間複雜度: O(n) - n 為 t 的長度
空間複雜度: 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
    }
}

補充：Follow-up 多次查詢的預處理解法

如果有大量 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: 雙指標掃描是子序列判斷的標準做法
關鍵技巧: 子序列 vs 子字串——子序列不要求連續，只要求相對順序；Follow-up 預處理 + 二分搜尋可處理多次查詢