问题描述:
翻译数字串,类似于电话号码翻译:给一个数字串,比如12259,映射到字母数组,比如,1 -> a, 2-> b,... , 12 -> l ,... 26-> z。那么,12259 -> lyi 或 abbei 或 lbei 或 abyi。输入一个数字串,判断是否能转换成字符串,如果能,则打印所以有可能的转换成的字符串。
思路:采用深度优先,分别考虑用一个数字字符转换和两个字符转换,然后在进行后续的转换。
#include <iostream> using namespace std; // 深度优先输出 // str是待打印字符串,需要预先分配空间,至少是带转换字符串的长度 bool Num_transform(char *num_str , int s , int e , char *str , int index) { if(s > e) { if(index != 0) //转换到了数字串最尾 { str[index] = '\0'; cout<<str<<endl; return true; } return false; } if(num_str[s] == '0') //判断当前字符串区间起始是否是0 { return false; } // 取一个数组用于转换 char temp = 'a' + (num_str[s]-'1'); str[index] = temp; bool re1 = Num_transform(num_str , s+1 , e , str , index+1); // 取两个数字用于转换 bool re2 = false; if(s < e) { int offset = (num_str[s]-'0')*10+(num_str[s+1]-'0'); if(offset <= 26) { temp = 'a' + offset - 1; str[index] = temp; re2 = Num_transform(num_str , s+2 , e , str , index+1); } } return re1 || re2; } int main() { char *num_str = "12259"; char *str = new char[6]; if(!Num_transform(num_str , 0 , 4 , str , 0)) { cout<<"no string!!"<<endl; } system("pause"); return 0; }