[NC]116. 把数字翻译成字符串

🚩传送门：牛客题目
力扣题目

题目

有一种将字母编码成数字的方式：'a'->1, 'b->2', … , 'z->26'。现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足
进阶：空间复杂度 ，时间复杂度

解题思路：动态规划

👉 定义： 表示以下标 字符结尾的最多翻译方案数量。

对于第i个数字

• 如果能单独拿出来翻译，那么会有_dp[i-1]_种
• 如果能够和前面的组合，那么会有_dp[i-2]_种

细节在于，单独翻译的数字可以是[1,9]之间，但能够组合的数字如果个位在[7,9]之间那么十位必须是1，如果各位是[0,6]之间，那么十必须是[1,2]之间。

状态转移方程：

复杂度分析

时间复杂度： ，其中 是数组长度。

空间复杂度： ，其中 是数组长度。

我的代码

    public int solve (String nums) {
        // write code here
        int n=nums.length();
        int[] dp=new int[n];    // 从0到下标i的字符串,一共有多少种翻译结果
        if(nums==null||n==0) return 0;
        if('1'<=nums.charAt(0) && nums.charAt(0)<='9')
            dp[0] = 1;
        for(int i=1;i<n;i++){
            if('1'<=nums.charAt(i) && nums.charAt(i)<='9')
                dp[i] =dp[i-1];
            if((('0'<=nums.charAt(i) && nums.charAt(i)<='6') 
                && ('1'==nums.charAt(i-1) || nums.charAt(i-1)=='2'))
              ||
               (('0'<=nums.charAt(i) && nums.charAt(i)<='9') 
                && ('1'==nums.charAt(i-1)))
              )
                   if(i>1)
                        dp[i] += dp[i-2];
                    else
                        dp[i] += 1;
            }
        return dp[n-1];
        }
}