题目描述
- 给定一个数字，我们按照如下规则把它翻译为字符串： 0翻译成 'a'，1 翻译成 'b'， ......，11 翻译成 'l'，25 翻译成 'z'
- 一个数字可能有多个翻译
- 例如， 12258 有 5 种不同的翻译，分别是 'bccfi'，'bwfi'，'bczi'，'mcfi'，'mzi'
- 请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法
题目解读
代码
#include<iostream>
using namespace std;
class Solution {
public:
int Core(const string& number){
int length = number.length();
int *counts = new int[length]; // 记录从字符串的每个位置开始翻译的翻译种树
int count = 0;
for (int i = length-1; i >= 0; i--) // 自底向上，避免求解重复子问题
{
count = 0;
if (i < length-1){
count = counts[i+1];
}
else{ // 从末尾开始翻译只有一种
count = 1;
}
if(i < length-1){
int digit1 = number[i] - '0';
int digit2 = number[i+1] - '0';
int converted = digit1*10 + digit2;
if (converted >= 10 && converted <= 25) // 判断i和i+1位置上的整数拼接是否满足翻译的要求
{
if(i < length-2){
count += counts[i+2]; // 满足要求时，从 i 位置开始翻译的种树还包括从 i+2 开始翻译的种树
}
else{
count += 1; // 从倒数第二个数开始翻译，
}
}
}
counts[i] = count;
}
count = counts[0];
delete[] counts;
return count;
}
int getTranslationCount(int number){
if(number < 0){
return 0;
}
return Core(to_string(number));
}
};
int main(){
Solution ss;
cout<<ss.getTranslationCount(12258)<<endl;
}
总结展望
