【JZ46 把数字翻译成字符串】

本文主要是介绍【JZ46 把数字翻译成字符串】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
我们把一个字符串编码成一串数字，再考虑逆向编译成字符串。
由于没有分隔符，数字编码成字母可能有多种编译结果，例如 11 既可以看做是两个 'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ，因为 0 不能编译成任何结果。
现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0 < n ≤ 90
进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入： "12"返回值：2说明：2种可能的译码结果（”ab” 或”l”）

示例2

输入： "31717126241541717"返回值：192说明：192种可能的译码结果

分析：

首先对数据进行分类，对于空字符串、首字符为‘0’的字符串，以及‘0’的前一位不是‘1’或者‘2’的字符串，输出0；
建立一个动态数组dp[len+1],用于存储有几种译码结果。dp[0]=1,dp[1]=1。

1）若第k个字符和第 k-1 个字符能够组合成a到z的合法字符，则dp[k+1]=dp[k]+dp[k-1];

2）若无法组成合法字符，则译码结果没有增加，dp[k+1]=dp[k];

3）若第k个字符和第 k-1 个字符中有 ‘0’，则无法产生新的译码方式，dp[k+1]=dp[k];

在这里插入图片描述

代码：

class Solution {public:int solve(string nums) {int len = nums.size();if (len == 0)return 0;for (int k = 0;k < len;k++){if (nums[k]=='0'){if (k == 0)return 0;else if (nums[k-1] != '1' && nums[k-1] != '2')return 0;}}//如果0位于第一位或者0的前面不是1或者2，则无法进行译码int dp[len+1],temp;dp[0] = 1;dp[1] = 1;for (int k=1;k<len;k++){temp=(nums[k]-'0')+(nums[k-1]-'0')*10;if (temp > 0 && temp <= 26 && nums[k]!= '0'&& nums[k-1] != '0')dp[k+1] = dp[k]+dp[k-1];elsedp[k+1] = dp[k];}return dp[len];}
};