「递归英文」电话号码转对于英文单词 --编程之美（递归与非递归版）

递归英文

此题来着编程之美

对如非全键盘的手机上的数字，每个数字都对应一些字母，比如2对应ABC，3对应DEF.........，8对应TUV，9对应WXYZ，要求对一段数字，输出其代表的所有可能的字母组合，如5869，可能代表JTMW、JTMX.................

//对于01，我翻了下书，发现其根本没有处理，出现01直接没有结果！在此，以下加入,只需判断为 0 ，1 即继续遍历下一层，当结果的index索引不动即可，具体参见代码.

//以下用自己的思路编写，处理了01没有对于字母的情况！！思路采用深搜！dfs！注意一些细节

#include <iOStream>
#include <string>
using namespace std;

char num_str[10][5] =
{
	"",
	"",
	"abc",
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz"
};
char * num_to_str(char *num,char *res,int level,int index,int &count);
char *num_to_str_final(char *num,char *res);
int main()
{
	char num_char[10],res[10];
	cin>>num_char;
	
	num_to_str_final(num_char,res);
	
	return 0;
}

char *num_to_str_final(char *num,char *res)
{
	if (num == NULL||num[0] == '\0')
	{
		return NULL;
	}
	int count = 0;
	num_to_str(num,res,0,0,count);
	cout<<"total num :"<<count<<endl;
	return res;
}
char * num_to_str(char *num,char *res,int level,int index,int &count)
{
	if (num[level] == '\0')
	{
		count++;
		res[index] = '\0';
		cout<<res<<endl;
		return res;
	}
	else if (num[level] == '0'||num[level] == '1')
	{
		 
		num_to_str(num,res,level+1,index,count);//无字符
	}
	else
	{
		for (int i = 0;num_str[num[level]-'0'][i] != '\0';i++)
		{
			res[index] = num_str[num[level]-'0'][i];
			num_to_str(num,res,level+1,index+1,count);
		}
	}
	
}

以下为非递归版本，要对0,1特殊处理 --- 跟书上的思路有些不同，书上直接回溯，不进行下溯，更快。不过此题目的是总结这类题型的一般做法！

总之有递归版本转非递归，把握好递归树，

有3个部分：

1、选择即下溯

2、退出条件

3、回溯，其中含2部分，1.到达最底层的回溯问题，2.超过有下面回溯上来，导致分支数超出本来大小，继续回溯的情况。

详情请看代码。由于增加了01的特殊处理，如果正常情况，把01的抹掉，看起来就很直观！

大家也可以参考：图着色--非递归实现即为相似，基本上可以总结出一个套路，或模板，只需大家注意细节！

#include <iostream>
#include <string>
#include <cstring>
#include "vld.h"
using namespace std;

char num_str[10][5] =
{
	"",
	"",
	"abc",
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz"
};

void print(char *res);
int num_to_str(char *num);
int main()
{
	char num[20];
	cin>>num;
	cout<<num_to_str(num);

	return 0;
}

int num_to_str(char *num)
{
	int level = 0;
	int len = strlen(num);
	int *branch = new int[len+1];
	char *res = new char[len+1];//存放'/0’
	 
	int res_index = 0;
	int count = 0;

	memset(branch,0,sizeof(int)*(len+1));
	memset(res,0,sizeof(char)*(len+1));

	while(level >= 0)
	{
		
		if (num[level] != '\0' )//正常的！
		{
			if (num[level] == '0'||num[level] == '1')//例外的占据空间的
			{
				if (branch[level] == 0)
				{
					level ++;
				}
				else
				{
					branch[level] = 0;
					level -- ;
					if(level >= 0)//上一个，注意是否level == -1
					branch[level]++;
				}
				
			}
			else if (num_str[num[level]-'0'][branch[level]] == '\0')	//回溯
			{

				branch[level] = 0;//重置
				level --;
				if(level >= 0)//上一个，注意是否level == -1
				branch[level]++;//下一个分支开始
				res_index--;
			}		 
			else
			{
				res[res_index] = (num_str[num[level]-'0'][branch[level]]); 
				res_index++; 
				level++;
			}
		}
		else//终止
		{

			count++;
			res[res_index] = '\0';
			print(res);
			res_index--;
			level --;		
			branch[level]++;//下一个分支开始	
		}

	}

	delete []branch;
	delete []res;
	return count;
}

void print(char *res)
{
	for (int i = 0;res[i] != '\0';i++)
	{
		cout<<res[i];
	}
	if (*res != '\0')
	{
		cout<<endl;	
	}
	
}

电话号码转对于英文单词 --编程之美（递归与非递归版）

递归英文

相关阅读

栏目导航

推荐阅读

热门阅读

电话号码转对于英文单词 --编程之美 （递归与非递归版）

递归英文

相关阅读

栏目导航

推荐阅读

热门阅读

电话号码转对于英文单词 --编程之美（递归与非递归版）