// 面试题46：把数字翻译成字符串
// 题目：给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成"a"，1翻
// 译成"b"，……，11翻译成"l"，……，25翻译成"z"。一个数字可能有多个翻译。例
// 如12258有5种不同的翻译，它们分别是"bccfi"、"bwfi"、"bczi"、"mcfi"和
// "mzi"。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
#include <iostream>
#include <string>
#include <vector>using namespace std;
char* chars = "abcdefghijklmnopqrstuvwxyz";//translate the number to string
int Number2String(const string& number);int Number2String(int num)
{//robustif(num < 0){return 0;}//initstring numberInString = to_string(num);return Number2String(numberInString);
}string GetChar(char a);
//没有使用递归，因为递归会有很多重复的计算
int Number2String(const string& number)
{int len = number.length();int* counts = new int[len];//缓存只可能出现的两种情况vector<string> temps(2);//缓存出现的字母组合vector<string> temp1;vector<string> temp2;vector<string> temp3;//最终的结果vector<string> results;int count = 0;for (int i = len - 1; i >= 0; i--){count = 0;temps.clear();if (i < len-1){count = counts[i+1];}else{count =1;}//取到第一个字母，先不管它与其他数字的可能组合temps.push_back(GetChar(number[i]));if(i < len-1){int digit1 = number[i] - '0';int digit2 = number[i+1] - '0';int convert = digit1*10 + digit2;if(10<= convert && convert <= 25){if(i < len -2){count += counts[i+2];//大于第二位的数}else{count += 1;//说明是第二位，和第一位可以组成一个字母}//当前数和后一位数可以组合时，记录该字母temps.push_back(GetChar(convert+'0'));}}//第一个和第二个可以直接算出，然后缓存起来，从第三个开始，如果有两种可能，则分别和前面的两个缓存结合//temp1 缓存上两个，与第二种情况结合， 即两个数字可以组成一个字母//temp2 缓存上一个，与第一种情况结合if(i == len -1){temp1.push_back(temps[0]);}else if (i == len -2){temp2.push_back(temps[0] + temp1[0]);if(temps.size() == 2){temp2.push_back(temps[1]);}}else{//添加可能的字母temp3.clear();for(auto value: temp2){temp3.push_back(temps[0]+value);}if(temps.size() == 2){for(auto value: temp1){temp3.push_back(temps[1]+value);}}//调整缓存temp1 = temp2;temp2 = temp3;}counts[i] = count;}results = temp3;for(auto value: results){cout << "results ===> " << value << endl;}count = counts[0];delete[] counts;return count;
}string GetChar(char a)
{int index = a - '0';//字符转字母，居然还是一个费劲的过程。//先创建一个string，然后修改这个string，从而得到结果string str = "a";str[0] = chars[index];return str;
}