题目描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
Example1:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
限制
- 0 <= num < 2^31
解题思路
- 跟爬梯子差不多
- 如果这个字母如果能单独翻译 即 dp[i] = dp[i - 1]
- 如果这个字母能和前一个组合翻译 需要加上 dp[i] += dp[i - 2];
class Solution {
public:
int translateNum(int num) {
string str = to_string(num);
int dp[str.size() + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i = 1; i <= str.size(); i++){
// 当前字符单独翻译时
if(str[i - 1] >= '0' && str[i - 1] <= '9'){
dp[i] = dp[i - 1];
}
// 当前字符和前一个字符组合翻译时
if(i > 1){
int temp = (str[i - 2] - '0') * 10 + (str[i - 1] - '0');
if(temp >= 10 && temp <= 25){
dp[i] = dp[i] + dp[i - 2];
}
}
}
return dp[str.size()];
}
};
