把数字翻译成字符串（动态规划）

题意

给定一个数字串,它是由a-z映射成1-26得到的,问它的原文有多少种可能

思路分析

能被反向的条件

因为是a-z映射成1-26得到的

所以每个被反向映射的值一定在1-26之间

所以判断是1位还是2位,且值满足范围,没有前导0

能被反向的1位数

只有1-9可以被反向编译

所以

nums[i] != '0'

能被反向的2位数

10-26可以被反向

nums[i-1] != '0' && (nums[i-1]-'0')*10+(nums[i]-'0') <= 26

递推关系

设dp[i]表示从开始到第i位能被反向的方案数那么有

if(可一位反向(i)){
    dp[i] += dp[i-1];
}
if(可两位反向(i-1,i)){
    dp[i] += dp[i-2];
}

边界处理

主要是初始化时, 和判断两位

对于初始化:空字符串认为是可以被处理,方案数为1

对于两位判断,因为涉及到i-1,所以要判断i>0

样例数据示例

以样例数据1为例,"12"

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    int solve(string nums) {
        // write code here
        vector<int> res(nums.size()+1,0);
        res[0] = 1;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] != '0') { // 一个数字译为一个字符
                res[i+1] += res[i];
            }
            // 两个数字译为一个字符
            if(i > 0 && nums[i-1] != '0' && (nums[i-1]-'0')*10+(nums[i]-'0') <= 26) {
                res[i+1] += res[i-1];
            }
        }
        return res[nums.size()];
    }
};

复杂度分析

空间复杂度: 存储状态数组大小和原数组一致,所以空间复杂度为$O(n)O(n)$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为$O(n)O(n)$