solution.md

# 解码方法

<p>一条包含字母 <code>A-Z</code> 的消息通过以下映射进行了 <strong>编码</strong> ：</p>
<pre>'A' -> 1'B' -> 2...'Z' -> 26</pre>
<p>要 <strong>解码</strong> 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，<code>"11106"</code> 可以映射为：</p>
<ul>
    <li><code>"AAJF"</code> ，将消息分组为 <code>(1 1 10 6)</code></li>
    <li><code>"KJF"</code> ，将消息分组为 <code>(11 10 6)</code></li>
</ul>
<p>注意，消息不能分组为  <code>(1 11 06)</code> ，因为 <code>"06"</code> 不能映射为 <code>"F"</code> ，这是由于 <code>"6"</code> 和
    <code>"06"</code> 在映射中并不等价。
</p>
<p>给你一个只含数字的 <strong>非空 </strong>字符串 <code>s</code> ，请计算并返回 <strong>解码</strong> 方法的 <strong>总数</strong> 。</p>
<p>题目数据保证答案肯定是一个 <strong>32 位</strong> 的整数。</p>

<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>s = "12"<strong><br />输出：</strong>2<strong><br />解释：</strong>它可以解码为 "AB"（1 2）或者 "L"（12）。</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>s = "226"<strong><br />输出：</strong>3<strong><br />解释：</strong>它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>s = "0"<strong><br />输出：</strong>0<strong><br />解释：</strong>没有字符映射到以 0 开头的数字。含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。</pre>
<p><strong>示例 4：</strong></p>
<pre><strong>输入：</strong>s = "06"<strong><br />输出：</strong>0<strong><br />解释：</strong>"06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。</pre>

<p><strong>提示：</strong></p>
<ul>
    <li><code>1 <= s.length <= 100</code></li>
    <li><code>s</code> 只包含数字，并且可能包含前导零。</li>
</ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c
int main()
{
    Solution sol;
    int res;
    string s = "226";
    res = sol.numDecodings(s);
    cout << res;
    return 0;
}
```

## 答案

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


### A

```c
class Solution
{
public:
    int dp(string &s, int i, int j)
    {
        int n = j - i + 1;
        if (n == 0)
            return 0;
        if (n == 1)
            return s[i] == '0' ? 0 : 1;
        if (n == 2)
        {
            if (s[i] == '0')
                return 0;
            if (s[i] > '2')
                return s[j] == '0' ? 0 : 1;
            if (s[i] == '2' && s[j] > '6')
                return 1;
            if (s[j] == '0')
                return 1;
            return 2;
        }
        if (s[i] > '2')
            return dp(s, i + 1, j);
        if (s[i] == '2')
        {
            if (s[i + 1] == '0')
                return dp(s, i + 2, j);
            else if (s[i + 1] < '7')
                return dp(s, i + 1, j) + dp(s, i + 2, j);
            else
                return dp(s, i + 1, j);
        }
        if (s[i] == '0')
            return 0;
        if (s[i + 1] == '0')
            return dp(s, i + 2, j);
        return dp(s, i + 1, j) + dp(s, i + 2, j);
    }
    int numDecodings(string s)
    {
        return dp(s, 0, s.size() - 1);
    }
};
```

### B

```c
class Solution
{
public:
    int numDecodings(string s)
    {
        vector<int> nums(s.size());
        if (s[0] == '0')
        {
            return 0;
        }
        nums[0] = 1;

        if (s.size() > 1)
        {
            if (s[1] != '0')
            {
                nums[1] += 1;
            }
            if ((s[0] - '0') * 10 + (s[1] - '0') <= 26)
            {
                nums[1] += 1;
            }
        }

        for (int i = 2; i < s.size(); i++)
        {
            if (s[i] != '0')
            {
                nums[i] += nums[i - 1];
            }
            if (s[i - 1] != '0' && ((s[i - 1] - '0') * 10 + (s[i] - '0') <= 26))
            {
                nums[i] += nums[i - 2];
            }
        }
        return nums[s.size() - 1];
    }
};
```

### C

```c
class Solution
{
public:
    int numDecodings(string s)
    {
        int n = s.size();
        if (s.empty())
            return 0;
        if (s[0] == '0')
            return 0;
        vector<int> info(n + 1, 0);
        info[0] = 1;
        info[1] = 1;
        for (int i = 2; i < n + 1; ++i)
        {
            if (s[i - 1] != '0')
                info[i] += info[i - 1];
            if (s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10")
                info[i] += info[i - 2];
        }
        return info[n];
    }
};
```