题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0 翻译成 a
,1 翻译成 b
,……,11 翻译成 l
,……,25 翻译成 z
。
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译,它们分别是 bccfi
、bwfi
、bczi
、mcfi
和 mzi
。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
样例
输入:"12258"
输出:5
算法1 dfs
C++ 代码
class Solution {
public:
int total = 0;
void dfs(string s, int n){
if(n == s.size()){
total ++;
return ;
}
dfs(s, n + 1);
if(n + 1 < s.size()){
int a = s[n] - '0';
int b = s[n + 1] - '0';
if(a && a * 10 + b < 26) dfs(s, n + 2);
}
}
int getTranslationCount(string s) {
int n = s.size();
dfs(s, 0);
return total;
}
};
算法2 dp
C++ 代码
class Solution {
public:
int getTranslationCount(string s) {
if(s.empty()) return 0;
s = ' ' + s;
int len = s.size();
int dp[len];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < len; i ++){
dp[i] = dp[i - 1];
int k = s[i] - '0';
int k1 = s[i - 1] - '0';
if(k1 * 10 + k <= 25 && k1) dp[i] += dp[i - 2];
// cout << dp[i] << endl;
}
return dp[len - 1];
}
};