解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2

解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:

输入: "226"
输出: 3

解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        if (s[0] == '0') return 0;
        int* dp = new int[s.size()];
        dp[0] = 1;
        for (int i = 1; i < s.size(); ++i) {
            dp[i] = 0;
            // 当前点不为0时候
            if (s[i] != '0') {
                // 前一个点不为0时候
                if (s[i - 1] != '0') {
                    dp[i] += dp[i - 1];
                    int temp = atoi((s.substr(i - 1, 2).c_str()));
                    if (temp <= 26 && temp > 0) {
                        dp[i] += i > 1 ? dp[i - 2] : 1;
                    }
                }
                // 前一个点为0时候
                else {
                    // 前两个点和前一个点是否能组成 "10" or "20"
                    if (i > 1 && (s[i - 2] == '1' || s[i - 2] == '2')) {
                        dp[i] = dp[i - 2];
                    }
                    // 不能则解码失败
                    else {
                        return 0;
                    }
                }

            }
            // 当前点为0时候
            else {
                // 判断当前点和前一个点是否能组成 "10" or "20"
                if (s[i - 1] == '1' || s[i - 1] == '2') {
                    dp[i] = i > 1 ? dp[i - 2] : 1;
                }
                else  // 不能则解码失败
                    return 0;
            }

        }
        return dp[s.size() - 1];
    }
};

/*
// 超时

int numDecodings(string s) {
        return dfs(s, 0);
    }
    int dfs(const string &s, int index) {
        if(index >= s.size()) return 1;
        // 将该下标取一位
        int num1 = 0;
        if(s[index] != '0')
            num1 = dfs(s, index + 1);
        else return 0;
        // 将该点取两位
        int num2 = 0;
        if(index + 1 < s.size() && atoi((s.substr(index, 2)).c_str()) <= 26) {
            num2 = dfs(s, index + 2);
        }
        return num1 + num2;
    }
    
*/