剑指offer 把数字翻译成字符串
剑指offer 把数字翻译成字符串
题目
给定一个数字,我们按照如下规则把它翻译为字符串:
0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z。
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译,它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
样例
输入:"12258"
输出:5
参考答案
/**
* 1268
* 1 2 6 8
* 1 26 8
* 12 6 8
*
*/
class Solution {
public:
int getTranslationCount(string s) {
int n = s.size();
if(!n) return 0;
if(n==1) return 1;
vector<int> dp(n+1, 0);
dp[n-1] = 1;
for(int i=n-2;i>=0;i--){
dp[i] = dp[i+1];
if(s[i]=='1' || (s[i]=='2' && s[i+1]<'6')){
dp[i] += dp[i+2];
}
}
return dp[0];
}
};