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

方法：动态规划

1、遍历字符串，使用一个数组dp存储字符串不同位置结尾的译码结果次数，可以得到如下的状态转移方程

如果当前字符可以和前面一个字符组成一个译码结果：dp[i] = dp[i - 1] + dp[i - 2]

否则，dp[i] = dp[i - 1]

2、数组最后一个元素就为字符串的译码结果次数。

注意，当字符串中出现‘0’时，需要进行特殊处理

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    int solve(string nums) {
        // 特殊情况处理
        if (nums[0] == '0')
            return 0;
        for (int i = 1; i < nums.length(); i++)
            if (nums[i] == '0' && nums[i - 1] != '1' && nums[i - 1] != '2')
                return 0;

        vector<int> dp(nums.length() + 1, 1);
        for (int i = 2; i <= nums.length(); i++) {
            //在11-19，21-26之间的情况
            if ((nums[i - 2] == '1' && nums[i - 1] != '0') || (nums[i - 2] == '2' &&
                    nums[i - 1] > '0' && nums[i - 1] < '7'))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
};