[TOC]

一、题目描述

一条包含字母 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题算法

讲道理，递归由于调用栈的存在，我不是很会算时间复杂度跟空间复杂度，所以涉及到递归的算法一般我就不分析了。

1. 暴力法

思路：

不得不说，暴力法始终都是我们的思考手段之一，毕竟大力出奇迹。

由于使用了递归枚举，为了保证思路清晰，我们只需要看第一个字符即可：

• 若第一个字符无法与第二个字符构成合法编码。那第一个字符显然只有一种解释方式。
  于是整个编码串的解码方式数量等价于从第二个字符起的编码串的解码方式数量。

• 若第一个字符可以与第二个字符构成合法编码。那第一个字符显然有两种解释方式：

  • 将第一个字符单独解释，此整个编码串的解码数量等价于从第二个字符起的编码串的解码方式数量。
  • 将第一个字符与第二个字符联合解释，此整个编码串的解码数量等价于从第三个字符起的编码串的解码方式数量。

  整个字符串的解码方式为两种解释方式之和。

我们只需要注意如下情况：

• 当前后字符能组成0~9时，由于0无法解码只有0种解码方式，其余都是1种。
• 当前后字符能组成10～26时，10与20因为0不是合法字符只有1种解码方式，其余都是2种。
• 当前后字符能组成27～99时，10的倍数由于0不合法，只能为0种解码方式，其余都是1种。

代码：

class Solution {
public:
    int numDecodings(string s) {
        str = s;
        return dfs(0);
    }
    
    int dfs(int i) {
        if (i < str.size() && str[i] == '0')
            return 0;

        auto len = int(str.size()) - i;
        switch (len) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return valid(str[i], str[i + 1]) ? valid(str[i + 1]) ? 2 : 1 : valid(str[i + 1]) ? 1 : 0;
            default: {
                auto ans = dfs(i + 1);
                if (valid(str[i], str[i + 1]))
                    ans += dfs(i + 2);
                return ans;
            }
        }
    }

    inline bool valid(char ch) {
        return '0' < ch && ch <= '9';
    }

    inline bool valid(char lhs, char rhs) {
        auto num = (lhs - '0') * 10 + (rhs - '0');
        return 0 < num && num < 27;
    }
    
private:
    string str;
};

2. 记忆化搜索

思路：

考虑到暴力搜索的不足在于重复计算，如下图所示：

图1 重复计算示意图

既然问题找到了，那我们就好好思考下解决问题就行了呗。
避免重复计算的一个朴素的想法是，如果我计算了某个编码，能不能将该编码的解码方式的种类保存下来？这样一旦需要重复计算这个编码的时候，我直接把保存好的结果取出来，就能避免再次计算了。

好像这样有搞头诶？当前扫描到第个字符，我直接用表示从起的编码串的解码方式数量岂不美哉？

代码：

class Solution {
public:
    int numDecodings(string s) {
        str = s;
        val.resize(s.size(), -1);
        return dfs(0);
    }

    int dfs(int i) {
        if (i < str.size() && str[i] == '0')
            return 0;

        auto len = int(str.size()) - i;
        switch (len) {
            case 0:
                return 0;
            case 1:
                return 1;
            case 2:
                return valid(str[i], str[i + 1]) ? valid(str[i + 1]) ? 2 : 1 : valid(str[i + 1]) ? 1 : 0;
            default: {
                auto ans = 0;
                if (val[i + 1] == -1)
                    val[i + 1] = dfs(i + 1);
                ans = val[i + 1];
                if (valid(str[i], str[i + 1])) {
                    if (val[i + 2] == -1)
                        val[i + 2] = dfs(i + 2);
                    ans += val[i + 2];
                }
                return ans;
            }
        }
    }

    inline bool valid(char ch) {
        return '0' < ch && ch <= '9';
    }

    inline bool valid(char lhs, char rhs) {
        auto num = (lhs - '0') * 10 + (rhs - '0');
        return 0 < num && num < 27;
    }

private:
    vector<int> val;
    string str;
};

3. 动态规划

思路：

这一题其实是一道典型的动态规划题，类似于01背包，只不过我一开始没有看得出来，太菜了。

仔细看看上述暴力法和记忆化搜索中所使用的枚举方案，是不是隐约出现了的味道？
成了！状态转移方程都有了，这事成了！
不过如果用这转移方程的话，得像递归一样从编码串最右边开始算起了，有点不太习惯。还是转成从左往右计算比较顺手，那状态转移方程就变成了：

接着就差初始条件了，显而易见的是，

这里是想提及一个小技巧——状态压缩。由于我们看到状态转移方程中只有、、，所以我们可以直接使用三个变量，、、来和他们一一对应，省去了开辟整个数组所需要的时间和内存。

代码：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty())
            return 0;
        
        auto lhs = 1, rhs = valid(s[0]) ? 1 : 0;
        for (auto i = 1; i < s.size(); ++i) {
            auto cur = valid(s[i]) ? rhs : 0;
            if (valid(s[i - 1], s[i]))
                cur += lhs;
            lhs = rhs; rhs = cur;
        }
        return rhs;
    }
    
    inline bool valid(char ch) {
        return '0' < ch && ch <= '9';
    }
    
    inline bool valid(char lhs, char rhs) {
        auto num = (lhs - '0') * 10 + (rhs - '0');
        return 9 < num && num < 27;
    }
};