# Decode Ways

> A message containing letters from A-Z is being encoded to numbers using the following mapping:
>
> 'A' -> 1
>
> 'B' -> 2
>
> ...
>
> 'Z' -> 26
>
> Given an encoded message containing digits, determine the total number of ways to decode it.
>
> For example,
>
> Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
>
> The number of ways decoding "12" is 2.

## Thoughts

给定一个由数字组成的字符串，数字可以转化成对应的字母(e.g. 1->A, 2->B, ...,26->Z)，问一共有多少种潜在的转化方法。根据字符串长度分成了N步，每步action为把S\[i]或S\[i - 1: i]转化成字母，因此DP\[i]表前i个字符有多少种转化方式。字符串为空时看作有1种转化方式。由于只与前两种状态有关，用size为3的滚动数组节约空间。

## Code

```cpp
/*
 * @lc app=leetcode id=91 lang=cpp
 *
 * [91] Decode Ways
 */

// @lc code=start
class Solution {
public:
    int numDecodings(string s) {
        int N = s.size();
        vector<int> dp(3, 0);
        dp[0] = 1;
        for (int i = 1; i <= N; ++i) {
            dp[i % 3] = 0;
            if (i != 1 && s[i - 2] != '0') {
                const auto v = stoi(s.substr(i - 2, 2));
                if (v <= 26 && v >= 1) dp[i % 3] = dp[(i - 2) % 3];
            }
            if (s[i - 1] > '0') dp[i % 3] += dp[(i - 1) % 3];
        }
        return dp[N % 3];
    }
};
// @lc code=end


```