115. Distinct Subsequences

Hard

Description

給定字串 s 和 t，回傳 s 的子序列中等於 t 的個數。子序列是從原字串中刪除若干字元（可以不刪）後得到的序列。

Example:

Input: s = “rabbbit”, t = “rabbit” Output: 3

Intuition#

若 s[i-1] == t[j-1]：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- dp[i-1][j-1]：用 s[i-1] 匹配 t[j-1]
- dp[i-1][j]：不用 s[i-1]
若不同：dp[i][j] = dp[i-1][j]（只能跳過 s[i-1]）
基底：dp[i][0] = 1（空字串 t 有一種匹配方式）

Approaches#

1: 2D DP Table#

概念: 建立 (m+1) x (n+1) 的表格，其中 m = s.length, n = t.length。
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val m = s.length
        val n = t.length
        val dp = Array(m + 1) { IntArray(n + 1) }
        for (i in 0..m) dp[i][0] = 1
        for (i in 1..m) {
            for (j in 1..n) {
                dp[i][j] = dp[i - 1][j]
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1]
                }
            }
        }
        return dp[m][n]
    }
}

⭐2: 1D DP（空間優化）#

概念: 用一維陣列從右到左更新（因為依賴 dp[j-1] 的舊值，必須逆向遍歷）。
時間複雜度: O(m * n)
空間複雜度: O(n)

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val n = t.length
        val dp = IntArray(n + 1)
        dp[0] = 1
        for (i in 1..s.length) {
            for (j in n downTo 1) {
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += dp[j - 1]
                }
            }
        }
        return dp[n]
    }
}

🔑 Takeaways#

Pattern: 子序列計數 DP — 「用」或「不用」當前字元的選擇
關鍵技巧: 空間優化時必須逆向遍歷以保護舊值；這題和 0/1 背包的逆向遍歷邏輯一致