# 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.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - 遞歸**

範例：`s = '2261'`

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

1. 單獨切分第一個字母： `2|216`&#x20;

   可能的組合為 (**2**, 2, 1, 6), (**2,** 2, 16), (**2**, 21, 6)
2. 切分前兩個字母： `22|16`&#x20;

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

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

```javascript
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 的方式讓測資可以通過

```javascript
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]`

```javascript
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`

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-91-Decode-Ways.html>" %}
