题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z。
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译,它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
数据范围
输入数字位数 [1,101]。
样例
输入:"12258"
输出:5
算法1
(自己写的动态规划) $O(n^2)$
表示:
优化:滚动数组
注意:$x_2$不能为0,就是不能存在$01,02,03$这种情况
C++ 代码
class Solution {
public:
int getTranslationCount(string s)
{
int sz = s.size();
if(sz ==1) return 1;
int f[3];
f[0] =1;
f[1]=1;
f[2]=0;
for(int i=2;i<=sz;++i)
{
int x1 = s[i-1]-'0';
int x2 = s[i-2]-'0';
// cout << x1 <<" " <<x2<<endl;
int sum = 10 * x2 +x1;
if(x2!=0 && sum>=0 && sum<=25) f[2] = f[1] + f[0];
//y总写法,合并条件,简洁
//if(sum>=10 && sum<=25) f[2]=f[1]+f[0];
else f[2]= f[1];
f[0]=f[1];
f[1]=f[2];
}
return f[2];
}
};