Decode Ways

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

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

/*
 * @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