LeetCode 解題筆記：940. Distinct Subsequences II

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


LeetCode 題目連結：940. Distinct Subsequences II

解題想法

困難題。題目給一個字串 $s$，要找出 $s$ 可以組合成幾個不重複的子字串，由於答案可能很大，要對 $10^9 + 7$ 取餘數。這題要用動態規畫解題，定義一個長度為 $26$ 的陣列 $dp$，$dp[i]$ 代表以第 $i$ 個字母結尾的子字串數量，依序從 $s$ 讀取字母 $c$，先取 $c$ 的索引值 $idx = ord(c) - ord('a')$，可以將 $c$ 接在原有的子字串後面或是自己獨立成新的子字串，因此更新方式為 $$ newdp[idx] = \left ( \sum_{i = 0}^{25} dp[i] \right ) + 1 \pmod{MOD} $$ 但是這樣的寫法每次更新時都要重新計算 $dp$ 的加總，速度不快。另外定義一個變數 $total$ 用來記錄 $dp$ 的加總，每次更新 $dp[idx]$ 時將 $dp[idx]$ 的值存到另一個變數 $prev$，更新方式改為 $$ dp[idx] = (total + 1) \pmod{MOD} $$ 接下來更新 $total$ $$ total = (total + dp[idx] - prev) \pmod{MOD} $$ 如果用 C 或 C++ 解題，為了避免在上一行相加時溢位以及相減時變成負數，要改成 $$ total = ((total + dp[idx]) \pmod{MOD} - prev + MOD) \pmod{MOD} $$

Python 程式碼

Runtime: 7 ms, beats 89.58%. Memory: 19.32 MB, beats 46.35%.

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        MOD = 10**9 + 7
        dp = [0] * 26  # 以各個小寫字母結尾的子字串數量
        total = 0  # 目前的子字串數量
        for c in s:  # 依序讀取字母
            idx = ord(c) - ord('a')  # 轉成 dp 串列索引值
            prev = dp[idx]  # 檢查到前一個字母時的值
            dp[idx] = (total + 1) % MOD  # 可以接在之前的子字串後面，或是自己獨立成新的子字串
            total = (total + dp[idx] - prev) % MOD  # 更新 total
        return total

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.95 MB, beats 62.00%.

class Solution {
public:
    int distinctSubseqII(string s) {
        const int MOD = 1000000007;
        vector<int> dp (26, 0);
        int total = 0;
        for(char c : s) {
            int idx = c - 'a';
            int prev = dp[idx];
            dp[idx] = (total + 1) % MOD;
            total = ((total + dp[idx]) % MOD - prev % MOD + MOD) % MOD;
        }
        return total;
    }
};

C 語言程式碼

Runtime: 3 ms, beats -%. Memory: 8.80 MB, beats 66.67%.

int distinctSubseqII(char* s) {
    const int MOD = 1000000007;
    int dp[26] = {0}, total = 0, n = strlen(s);
    for(int i = 0; i < n; i++) {
        int idx = s[i] - 'a';
        int prev = dp[idx];
        dp[idx] = (total + 1) % MOD;
        total = ((total + dp[idx]) % MOD - prev + MOD) % MOD;
    }
    return total;
}