91. Decode Ways

Leetcode

https://leetcode.com/problems/decode-ways/description/

題目

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)

• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

解答

• 方法一 - 遞歸

範例：s = '2261'

從前兩個字母切分來看會有兩種方式：

1. 單獨切分第一個字母： 2|216

   可能的組合為 (2, 2, 1, 6), (2, 2, 16), (2, 21, 6)

2. 切分前兩個字母： 22|16

   可能的組合為 (22, 1, 6), (22, 16)

所以要求出 2261 總共會有幾種解碼，就是 2|216 + 22|16 兩種組合加起來的數目，也就是五種

var numDecodings = function (s) {
    return getAns(s, 0);

    function getAns(s, start) {
        // 如果劃分到最後一個元素的後面，代表最後一個元素是有效的，回傳 1
        // p.s. 如果最後一個元素是 '0' 就不會走到這裡
        if (start === s.length) {
            return 1;
        }

        // 如果第一個字母是零，無法解碼回去，所以回傳 0
        if (s[start] === '0') {
            return 0;
        }

        // 1. 單獨切分第一個字母
        const ans1 = getAns(s, start + 1);
        // 2. 切分前兩個字母
        let ans2 = 0;

        // 判斷是否可以切分前兩個字母
        const isLessThen26 = checkIsLessThen26(s, start);
        if (isLessThen26) {
            ans2 = getAns(s, start + 2);
        }

        return ans1 + ans2;
    }

    function checkIsLessThen26(s, start) {
        return +`${s[start]}${s[start + 1]}` <= 26;
    }
};

結果：TLE

• 方法二 - 遞歸 + memorization

為了避免上一個方法有許多重複的計算，所以多增加使用 memo 的方式讓測資可以通過

var numDecodings = function (s) {
    const memo = {};

    return getAns(s, 0);

    function getAns(s, start) {
        if (memo[start]) {
            return memo[start];
        }

        if (start === s.length) {
            return 1;
        }

        if (s[start] === '0') {
            return 0;
        }

        const ans1 = getAns(s, start + 1);
        let ans2 = 0;

        const isLessThen26 = checkIsLessThen26(s, start);
        if (isLessThen26) {
            ans2 = getAns(s, start + 2);
        }

        // 添加 memo
        memo[start] = ans1 + ans2;

        return ans1 + ans2;
    }

    function checkIsLessThen26(s, start) {
        return +`${s[start]}${s[start + 1]}` <= 26;
    }
};

• 方法三 - DP

DP[i] 代表從第 i 個元素開始到最後一個元素為止，總共可能的解碼方式

所以按照方法一統整出來的邏輯 => DP[i] = DP[i+1] + DP[i+2]

var numDecodings = function (s) {
    const dp = [];
    // 1. 初始化最後一個元素後面的元素 dp 為 1
    dp[s.length] = 1;

    // 判斷最後一個元素的 dp
    if (s[s.length - 1] === '0') {
        dp[s.length - 1] = 0;
    } else {
        dp[s.length - 1] = 1;
    }

    // 從倒數最後一個元素開始往前遍歷
    for (let i = s.length - 2; i >= 0; i--) {
        // 如果元素為 0，代表 dp 為 0 
        if (s[i] === '0') {
            dp[i] = 0;
            continue;
        }

        const ans1 = dp[i + 1];
        let ans2 = 0;

        const isLessThen26 = checkIsLessThen26(s, i);
        if (isLessThen26) {
            ans2 = dp[i + 2];
        }

        dp[i] = ans1 + ans2;
    }

    function checkIsLessThen26(s, i) {
        return +`${s[i]}${s[i + 1]}` <= 26;
    }

    return dp[0];
};

問題

1. 為什麼 dp[s.length] 初始化為 1？

假設 s = '213'

• dp[2] 等於 1

• dp[1] = dp[2] + dp[3] = 1 + dp[3]

  dp[1] 全部的組合有 (1, 3), (13)，總共兩種，所以為了要讓 dp[1] = dp[2] + dp[3] 的算式成立，會把 最後一個元素後面的 DP (dp[s.length]) 初始化為 1

參考資料

91. Decode Ways · leetcodeleetcode.wang