## [91\. Decode Ways](https://leetcode.com/problems/decode-ways/)

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.

**Example 1:**

**Input:** s = "12"
**Output:** 2
**Explanation:** "12" could be decoded as "AB" (1 2) or "L" (12).

**Example 2:**

**Input:** s = "226"
**Output:** 3
**Explanation:** "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

**Example 3:**

**Input:** s = "06"
**Output:** 0
**Explanation:** "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

**Constraints:**

- `1 <= s.length <= 100`
- `s` contains only digits and may contain leading zero(s).

狀態轉移方程：

dp[i] = dp[i - 1]             if s[i - 1] != '0'
      + dp[i - 2]             if 10 <= stoi(s.substr(i - 2, 2)) <= 26

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        // dp 數列代表的是 s 的前 i 個位置可以被解碼的次數
        vector<int> dp(n + 1);
        
        // 起始值為 1，第 0 位可以被解碼
        dp[0] = 1;

        // 0 開頭的數字不能被解碼，所以要算 0 次
        // 其他數字開頭的話，算 1 次
        dp[1] = (s[0] == '0' ? 0 : 1);
        
        // 迭代從第 2 個位置開始
        // 也就是 s = "12" 的話，會從下標的地方開始算
        //             ^
        for(int i = 2; i < n + 1; i++) {
            // 考慮一個數字的情況，如果前一個位置不等於 0
            // 延續上一個可以解碼的次數：dp[i] = dp[i - 1]
            if(s[i - 1] != '0')
                dp[i] = dp[i - 1];

            // 考慮兩個數字的情況
            int twoDigits = stoi(s.substr(i - 2, 2));

            // 如果符合 10 ~ 26 之間，加上 dp[i - 2] 的結果
            if(10 <= twoDigits && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

:::success
- 時間複雜度：$O(N)$
- 空間複雜度：$O(N)$
:::