LeetCode 解題筆記：115. Distinct Subsequences

作者：王一哲
日期：2026年9月6日


LeetCode 題目連結：115. Distinct Subsequences

解題想法

困難題。題目給兩個字串 $s$、$t$，要計算 $s$ 的子字串之中有幾個等於 $t$，字串長度最長為 $1000$，要用動態規畫解題。

假設 $s$ 的長度為 $m$，$t$ 的長度為 $n$，開一個長度為 $(m+1) \times (n+1)$ 的二維陣列 $dp$，初始值先設為 0，$dp[i][0] = 1$，$dp[i][j]$ 代表檢查到 $s[i-1]$ 及 $t[j-1]$ 時，$s[0]$ 到 $s[i-1]$ 共有幾個子字串等於 $t[0:j]$。用兩層 for 迴圈更新 $dp$，外層跑 $i = 1$ 到 $i = m$，內層跑 $j = 1$ 到 $i = n$，如果 $s[i-1] == t[j-1]$，$dp[i][j] = dp[i-1][j-1] + dp[i-1][j]$；反之，$dp[i][j] = dp[i-1][j]$。由於更新時只需要用到前一次的狀態，可以用滾動陣列節省記憶體。由於答案很大，如果用 C 或 C++ 解題，$dp$ 的格式要用 unsigned long 才不會溢位。

Python 程式碼

二維陣列。Runtime: 419 ms, beats 49.82%. Memory: 75.56 MB, beats 56.33%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        dp = [[1] + [0]*n for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

滾動陣列。Runtime: 213 ms, beats 85.86%. Memory: 19.53 MB, beats 82.38%.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # 動態規畫，prev[j] 代表 s 之中等於 t[0:j] 的子字串數量
        m, n = len(s),  len(t)
        prev = [1] + [0]*n  # 前一個狀態，prev[0] = 1，空字串
        for c in s:  # 由 s 依序取出字母
            curr = [1] + [0]*n # 現在的狀態 curr[0] = 1，空字串
            for j in range(1, n+1):  # 掃過 t 的每個字母
                if t[j-1] == c:  # 如果 t[j-1] 等於 c
                    curr[j] = prev[j-1] + prev[j]  # 長度為前一個狀態索引值 j-1, j 相加
                else:  # 反之，繼承 prev[j]
                    curr[j] = prev[j]
            prev, curr = curr, prev  # 交換資料
        return prev[-1]  # 答案在 prev 最後一項

C++ 程式碼

二維陣列。Runtime: 30 ms, beats 58.87%. Memory: 44.40 MB, beats 20.60%.

class Solution {
public:
    int numDistinct(string s, string t) {
        // 動態規畫，dp[i][j] 代表 s[0:i] 範圍內可以組合出等於 t[0:j] 的子字串數量
        int m = (int)s.size(), n = (int)t.size();
        vector<vector<unsigned long>> dp (m+1, vector<unsigned long> (n+1, 0));
        for(int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        // 掃過 s 及 t，更新 dp，答案在 dp[m][n]
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }
};

滾動陣列。Runtime: 23 ms, beats 77.66%. Memory: 43.63 MB, beats 41.76%.

class Solution {
public:
    int numDistinct(string s, string t) {
        // 動態規畫，prev[j] 代表前一個狀態中以組合出等於 t[0:j] 的子字串數量
        int m = (int)s.size(), n = (int)t.size();
        vector<unsigned long> prev (n+1, 0);
        prev[0] = 1;
        // 掃過 s 及 t，更新 dp，答案在 prev[n]
        for(int i = 1; i <= m; i++) {
            vector<unsigned long> curr (n+1, 0);
            curr[0] = 1;
            for(int j = 1; j <= n; j++) {
                if (s[i-1] == t[j-1]) {
                    curr[j] = prev[j-1] + prev[j];
                } else {
                    curr[j] = prev[j];
                }
            }
            swap(prev, curr);
        }
        return prev[n];
    }
};

C 語言程式碼

Runtime: 36 ms, beats 6.32%. Memory: 16.64 MB, beats 30.86%.

int numDistinct(char* s, char* t) {
    int m = strlen(s), n = strlen(t);
    unsigned long dp[1001][1001];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= m; i++) {
        dp[i][0] = 1;
    }
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[m][n];
}