题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。
一个数字可能有多个翻译。例如12258有5种不同的翻译,它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
样例
样例
输入:"12258"
输出:5
算法1 (分治)
本题属于记数类DP
其实本题可以用递归来把问题规模缩小。
譬如12258
1单独翻译,问题就变成2258的次数
12一起翻译,问题就变成258.
也就可以用递归来解决伪代码如下:
int f(string num,int idx){ //f 的功能是放回从i开始(从左到右)的翻译个数
if(idx == num.size() -1){//边界 右边已经无数,即系空的,有一种方法
return 1;
}
int tmp = (num[idx]-'0') * 10 + num[idx+1] - '0';
if(tmp >= 10 && tmp <= 25) return f(num,idx+1) + f(num,idx+2);
else return f(num,idx+1);
}
本来想着TLE的,谁知道居然AC了。可能本台数据没有那么强。
谁知道,leetcode上面也过了。这个解法时间复杂度是$O(2^n)$
算法2 (动态规划)
C++ 代码
class Solution {
public:
int getTranslationCount(string s) {
int n = s.size();
s = '*' + s;
vector<int> f(n+1);
f[0] = 1;//空串有1种方法
for(int i = 1; i <= n; i++){
f[i] = f[i-1];
int tmp = ((s[i-1] - '0') * 10 + s[i] - '0');
if(tmp >= 10 && tmp <= 25)
f[i] += f[i-2];
}
return f[n];
}
};