91. Decode Ways

題目網址：https://leetcode.cn/problems/decode-ways/

題意：給一只含數字的非空 string s，計算並返回解碼的方法數

一則包含字母 A-Z 的訊息透過以下 mapping 進行編碼:

要解碼已編碼的訊息, 其所有數字必須基於上述 mapping 的方法，反向 mapping 回字母（可能有多種方法）。例如 : “11106” 可以 mapping 為：

• AAJF 將訊息分組為 (1 1 10 6)
• KJF 將訊息分組為 (11 10 6)

注意：訊息並不能分組為 (1 11 06), 因為 06 並不能 mapping 為 F, 這是因為 6 和 06 在 mapping 中並不等價

答案保證符合 32-bit 整數的範圍

Solution 1：（TLE 無法通過）

想法：利用 DFS, 其中每個 char 都有兩種選擇：

• 自己一組, 前提是自己不能為 '0'。若為 '0', 則一定要跟其他 char 一組
• 自己 + 後面一個 char 一組, 前提是 "10" <= substring <="26"

class Solution {
public:
    int numDecodings(string s) {
        const int n = s.size();
        dfs(s, 0, n);
        return res;
    }

private:
    int res = 0;

    void dfs(const string& s, const int i, const int n){
        if (i == n) {
            ++res;
            return;
        }

        // 不能自己一組
        if (s[i] == '0') {
            return;
        }

        // 不為 '0', 則可自己一組
        dfs(s, i + 1, n);

        if (i + 1 < n) {
            // 兩個 char 一組, 則必須介於 10 ~ 26 之間
            if (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')) {
                dfs(s, i + 2, n);
            }
        }
    }
};

• time：$O(n\cdot 2^n)$
  • $O(2^n)$ : 每一個 char 有兩種選擇, 一種是自己一組, 另外是和後面一個 char 一組, 總共 $2^n$ 種
  • 建構每一種狀況需花 $O(n)$ time
• space：$O(n)$ ➔ 取決於遞迴深度, 最大遞迴深度為 n

Solution 2：

想法：利用 DP, 其中 dp[i] 代表 s[0~(i-1)] 的解碼方法數

class Solution {
public:
    int numDecodings(string s) {
        const int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // empty string 不需解碼, 方法數為 1

        for (int i = 1; i <= n; ++i) {
            // 若不為 0, 則可以自己一組
            if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            // 前一個 char + 自己一組, 則 dp[i] += dp[i-2]
            if (i > 1) {
                if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) {
                    dp[i] += dp[i - 2];
                }
            }
        }

        return dp.back();
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(n)$ ➔ dp

Solution 3：

想法：改進 Solution 2, dp[i] 最多用到 dp[i - 1] 和 dp[i - 2], 因此不需要開到 n 個空間

class Solution {
public:
    int numDecodings(string s) {
        int one = 1, two = 1; // [two, one, cur]

        for (int i = 1; i <= s.size(); ++i) {
            // 若不為 0, 則可以自己一組
            int cur = (s[i - 1] == '0') ? 0 : one;

            if (i > 1) {
                if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) {
                    cur += two;
                }
            }

            two = one;
            one = cur;
        }

        return one;
    }
};

• time：$O(n)$ ➔ for loop
• space：$O(1)$ ➔ 只需常數空間