把数字翻译成字符串
描述
??有一种将字母编码成数字的方式：‘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种可能的译码结果
思路/解法
方式一
思路与方式二相同。
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
if(nums.length() == 1)return 1;
vector<int> dp(nums.length(),0);
dp[0] = 1;
if(nums[1] - '0' != 0)
{
int value = (nums[0] -'0')*10+(nums[1] -'0');
if(nums[0] != '0' && value < 27)
dp[1] = 2;
else
dp[1] = 1;
}
else
dp[1] = 1;
for(int i = 2;i<nums.length();i++)
{
//此时i位置的数字可以单独表示一个字符
if(nums[i] != '0')
dp[i] += dp[i-1];
int value = (nums[i-1] -'0')*10+(nums[i] -'0');
if(nums[i-1] != '0' && value < 27)
dp[i] += dp[i-2];
}
return dp[nums.length()-1];
}
};
方式二
思路分析
能被反向的条件
因为是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()];
}
};
