题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。
一个数字可能有多个翻译。例如12258有5种不同的翻译,它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
样例
输入:"12258"
输出:5
C++ 代码
class Solution {
public:
// 类比: 爬楼梯(dp)
// dp[n] = dp[n-1] + dp[n-2] 代表走到最后一个字符 有多少翻译方法?
// 1. 最后一个字符是1个字母作为翻译的话dp[n] = dp[n-1]
// 2. 最后一个字符和前一个字符组合翻译成的话 dp[n-2]种,而这种是有条件的当前一个字符是0的话,
// 不能被组合翻译, 只有 x >=10 && x <= 25 才符合条件
// 所以总共的个数为 dp[n]; n 代表多少个字符
int getTranslationCount(string s) {
// if(s.empty()) return 0;
int n = s.size();
vector<int> dp(n);
dp[0] = 1;
for(int i =1; i<=n; i++)
{
dp[i] = dp[i-1];
int k = (i>=2) * (s[i-2]-'0') * 10 + s[i-1]-'0'; // 需要保证有2位
if( k >= 10 && k <= 25) dp[i] += dp[i-2];
}
return dp[n];
}
};