LeetCode 91. Decode Ways [Medium] [C++] 解題筆記

這題給定一個都是數字的非空字串 s，每個數字可以對應到一個 A~Z 的字母，要我們求共有多少種解碼方式。

EX:

        'A' -> 1

        'B' -> 2
        ...
        'Z' -> 26

input:

        "226"

Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

想法:

        這題算是 70. Climbing Stairs 的變形題，是費氏數列的一種變化，這裡比較麻煩的是

因為有些組合是沒有辦法對應到一個字母的例如: 88 or 01，一般費氏數列的 dp 轉移方程

為 dp[i] = dp[i - 1] + dp[i - 2]，這邊可以想成 dp[i] 表示 s[0 : i - 1] 的解碼方法數，若 s[i - 1]不為 0

則 dp[i] 至少會有 dp[i - 1] 種方法，因為只要將 dp[i - 1] 的所有 decode方式加上 s[i - 1] 即可，而若

s[i - 2]與s[i - 1]可以組合成一個介於 10 ~ 26之間的數，表示 dp[i - 2] 的所有 decode方式加上 s[i - 2]s[i - 1]

對應到的字母可以再形成 dp[i - 2]種 decode 方式，而如果 s[i - 1] 是 '0' 表示它一定需要與前一個數字(s[i - 2])

組合才有可能做解碼，因此若 s[i - 1] 為 '0' 則至多只有可能有 dp[i - 2] 種方法。

而我們可以注意到這裡的 dp 其實只需要用到前兩個狀態的結果即可，因此除了一維陣列，也可以只用

三個變數做紀錄，達到 O(1) 的空間複雜度。

DP 轉移方程如下:

dp[i] = dp[i - 1], if s[i - 1] != '0' and (s[i-2]s[i-1] not  in 10~26)

        = dp[i - 2], if s[i - 1] == '0' and (s[i-2]s[i-1] in 10~26)

        = dp[i - 2] + dp [i - 1], if s[i - 1] != '0' and (s[i-2]s[i-1] in 10~26)

        = 0, if s[i - 1] == '0' and (s[i-2]s[i-1] not  in 10~26)

Complexity: O(n) time, O(n)/O(1) space.

完整程式碼:

解法一(O(n) space):

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') { return 0; }
        vector<int> dp(s.size() + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < dp.size(); i++) {
            dp[i] = (s[i - 1] == '0')? 0 : dp[i - 1];
            if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6') {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.size()];
    }
};

解法二(O(1) space):

class Solution {
public:
    int numDecodings(string s) {
        int pprev = 1;
        int prev = 1;
        int cur = 0;
        for (int i = 1; i < s.size()+1; i++) {
            cur = (s.at(i-1)=='0')? 0 : prev;
            if (i > 1) {
                if (s.at(i-2) == '1' || (s.at(i-2) == '2' && s.at(i-1) <= '6')) {
                    cur += pprev;
                }
            }
            pprev = prev;
            prev = cur;
        }
        
        return cur;
    }
};