题意
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
分析
base case : 对于数字 0~9, 只有一种翻译方法, 对于两位数 10 ~ 25, 有两种翻译方法。
对于数字 abcd…efg, 可能数字 ab 作为翻译的第一个字符,或者数字 a 作为翻译的第一个字符。
但是数字 ab 能够翻译成单个字符的条件是 ab > 9 && ab < 26, 根据以上可以写出递推式,这里使用记忆化搜索的写法
代码
class Solution {
public:
int f[15][15];
int translateNum(int num) {
if(num == 0)return 1;
memset(f, -1, sizeof f);
vector<int> nums;
while(num){
nums.push_back(num % 10);
num /= 10;
}
return count(0, nums.size()-1, nums);
}
int count(int low, int high, const vector<int>& nums){
if(f[low][high] != -1)return f[low][high];
if(low == high){
f[low][high] = 1;
return f[low][high];
}
if(high - low == 1){
f[low][high] = 1;
if(nums[low] + nums[high] * 10 < 26 && nums[low] + nums[high]*10 > 9)f[low][high] += 1;
return f[low][high];
}
f[low][high] = 0;
f[low][high] += count(low+1, high, nums);
if(nums[low] + nums[low+1] * 10 < 26 && nums[low] + nums[low+1]*10 > 9)f[low][high] += count(low+2, high, nums);
return f[low][high];
}
};