题解 | 把数字翻译成字符串

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // 0开头的字符串没有解码方式.
        if (nums.size() == 0 || nums[0] == '0')
            return 0;

        int n = nums.size();
        vector<int> dp(n, 0);

        dp[0] = 1;
        // 第二个字符在 1~9之间.
        if (nums[1] >= '1' && nums[1] <= '9') {
            if (nums[0] == '1' || nums[0] == '2')
                dp[1] = 2;
            else 
                dp[1] = 1;
        }
        // 第二个字符为 0.
        else {
            // 第一个字符是 1 or 2.
            if (nums[0] == '1' || nums[0] == '2') {
                dp[1] = 1;
            }
            // 第一个字符非 0 or 1. 
            else {
                return 0;
            }
        }

        for (int i = 2; i < n; ++i) {
            // 11-19 21-26 译码方式有两种.
            if ((nums[i-1] == '1' && (nums[i] >= '1' && nums[i] <= '9')) || (nums[i-1] == '2' && (nums[i] >= '1' && nums[i] <= '6'))) {
                dp[i] = dp[i-1]+dp[i-2];
            }
            // 一位数直接译码.
            else if (nums[i] >= '1' && nums[i] <= '9') {
                dp[i] = dp[i-1];
            }
            // 当前位为 0.
            else {
                // 10 or 20.
                if (nums[i-1] == '1' || nums[i-1] == '2') {
                    dp[i] = dp[i-2];
                }
                else {
                    return 0;
                }
            }
        }

        return dp[n-1];
    }
};

dp[i]表示到下标为 i 的数字为止，总的译码方式次数

初始化：

1. 第一个数字为0，不存在合法译码方式，直接return 0
2. 第一个数字不为0，dp[0] = 1，存在一种合法译码方式

1. 第二个数字为0
1. 第一个数字为1 or 2，dp[1] = 1，总共只有一种译码方式
2. 第一个数字不为1 or 2，不存在合法译码方式，直接return 0
2. 第二个数字不为0
1. 第一个数字为1 or 2，dp[1] = 2，总共有两种译码方式
2. 第一个数字不为1 or 2，dp[1] = 1，只存在一种译码方式

能够有两种译码方式的情况：

1. 数字为 11~19，21~26

能够有一种译码方式的情况：

1. 数字为 10，20
2. 前一位不为 1 or 2，当前位 1~9 ，或者前一位为 2，当前位 7~9

递推分类讨论：（按照是否能够有两种译码方式进行讨论）

1. 前一个数字为 1，当前数字为 1~9 或者 前一个数字为2，当前数字为1~6，则对于当前数字来说，存在两种译码方式，dp[i] = dp[i-1] + dp[i-2]
2. 不符合前一条规则，但是当前数字为 1~9，存在一种译码方式，dp[i] = dp[i-1]
3. 不符合前两条规则，说明当前数字为 0，判断前一个数字是否是 1 or 2，若不是，则不存在译码方式，若是，则存在一种译码方式，dp[i] = dp[i-2]

Day 2