[力扣_17] 电话号码的字母组合
题目入口：点击进入
相关算法：
- 深度优先搜索（递归回溯）——时间复杂度O(n^4),空间复杂度O(n^4)
- 广度优先搜索（借用队列实现）——时间复杂度O(n^4),空间复杂度O(n^4)
思路和算法：
这道题是道经典的搜索题，求最多的组合，我们可以用深搜来维护每一个字符，来获取每一个解，也可以用广搜来依次拼接所有的组合。
我们采用数组来做字母映射表，根本来说，数组就是key为非负整数的hash
我们可以将题意理解成将给定的数字串”翻译“成字符串，找出所有翻译可能，翻译每一个数组都有3或4种可能。
DFS（递归回溯）
我们可以从示例知道，这和排列组合相类似吧，假设给定数字串为”23“的话，那么两重循环即可枚举出所有的解，那么输入”234“就是三重循环....
同样，我们可以用递归来实现，递归的好处就是我们不必知道他有几重循环，到达给定数字串的尾端(当扫描指针越界时)，就生成了一个解，我们则将它加入解集当中，并且结束当前递归分支（return很重要）去别的分支，直到找到所有的解
递归树如下所示：
从上述可以得知，我们需要所有分支全部走一遍来拼接所有可能，则我们可以用循环加递归来实现DFS
详细演示套用”王尼玛“大神图示：
对于打印"2345"这样的字符串：
第一次递归就是上图中最下面的方格，然后处理完第一个字符2之后，将输入的字符改变成"345"并调用第二个递归函数
第二次递归处理3，将字符串改变成"45"后再次递归
第三次递归处理4，将字符串改变成"5"后继续递归
第四次递归处理5，将字符串改变成""后继续递归
最后发现字符串为空了，将结果放到列表中并返回
上面是从函数调用的角度去看的，而每次调用下一层递归时，都需要将本层的一些处理结果放到一个临时变量中，再传递给下一层，从这个变量层层传递的变化看，就像一棵树一样，这个算法的时间复杂度很高，是O(3^n)这个级别的，空间复杂度是O(n)
作者：wang_ni_ma
动图如下所示：
void DFS(char **ReturnStr,char *digits,char Value[][5],char *temp,int *returnSize,int len,int sleng)
{
if(len==sleng)//当len走到最后一位时，已经得出一个解，加入解集
{
*(ReturnStr+(*returnSize))=(char*)malloc(sizeof(char)*(sleng+1));
//申请当前解集空间
strcpy(*(ReturnStr+(*returnSize)),temp);
(*returnSize)++;//解集长度+1
return ;//返回！很重要！只要是递归，就需要return
}
else
{
for(int i=0;i< strlen(Value[digits[len]-'0']);i++)
//从字符开始
{
temp[len]=Value[digits[len]-'0'][i];//添加第一个字符
temp[len+1]='\0';
DFS(ReturnStr,digits,Value,temp,returnSize,len+1,sleng);
//当len走到最后的时候，还会退到上一层，此时循环再次到下一步
//相当于回溯，在len的位置替换字符
}
}
}
char ** letterCombinations(char * digits, int* returnSize){
int sleng=strlen(digits);
*returnSize=0;
if(strlen(digits)==0)
return NULL;
char Value[10][5] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };//映射表
char *temp=(char*)malloc(sizeof(char)*(sleng+1));
char **ReturnStr=(char**)malloc(sizeof(char*)*150);
DFS(ReturnStr,digits,Value,temp,returnSize,0,sleng);
return ReturnStr;
}关于上述的回溯算法，可以观看：关于回溯算法，你该了解这些此文，写的很棒！等我把数据结构撸完我也开始整算法
BFS(队列维护)
几乎所有BFS的题都需要辅助队列来做所有解集的寻找
先将输入的 digits 中第一个数字对应的每一个字母入队，然后将出队的元素与第二个数字对应的每一个字母组合后入队…直到遍历到 digits 的结尾。最后队列中的元素就是所求结果。
图示如下：
因为C语言需要提交的话，还需要将Queue中的元素放到一个字符串数组里边，我就不提交了，代码如下所示：
//LeetCode_17 BFS
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct QueueData
{
char String[10];
int sleng;
}QueueData;
typedef struct Queue
{
QueueData Data;
struct Queue* next;
}Queue;
typedef struct QLink
{
Queue *Q;
int size;
}QLink;
//队列维护
char Value[10][5] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//键值
void GetHeadQueue(QLink* Q, char* temp)//取出头端
{
Queue* p = Q->Q;
strcpy(temp, Q->Q->Data.String);
Q->Q = Q->Q->next;
free(p);
Q->size--;
}
void PutElemQueue(QLink* Q, char *temp)//插入尾端
{
if (Q->size == 0)
{
Q->Q = (Queue*)malloc(sizeof(Queue));
strcpy(Q->Q->Data.String, temp);
Q->Q->Data.sleng = strlen(Q->Q->Data.String);
Q->Q->next = NULL;
Q->size++;
}
else
{
Queue* p = Q->Q;
while (p->next) p = p->next;
p->next = (Queue*)malloc(sizeof(Queue));
strcpy(p->next->Data.String, temp);
p->next->next = NULL;
p->Data.sleng = strlen(temp);
Q->size++;
}
}
void ConnectString(char* t, char e,int len)//尾部添加字符
{
t[len] = e;
t[len + 1] = '\0';
}
void Visit(QLink Q)//检查遍历
{
Queue* p = Q.Q;
while (p)
{
printf("%s\n", p->Data.String);
p = p->next;
}
}
int main()
{
char S[255];
printf("请输入形式串：\n");
scanf("%s", S);
QLink Q;
Q.size = 0;
Q.Q = NULL;
int sleng = strlen(S);
for (int i = 0; i < sleng; i++)
{
int index = S[i] - '0';
int tempNumber = Q.size;
if(tempNumber==0)//初始化，当队列中无字母的时候，将首字符对应的键值插入队列
{
char temp[2];
for (int j = 0; j < strlen(Value[index]); j++)
{
temp[0] = Value[index][j];
temp[1] = '\0';
PutElemQueue(&Q, temp);
}
}
else
{
char temp[10];
for (int k = 0; k < tempNumber; k++)
{
GetHeadQueue(&Q, temp);//依次取出队列中的元素
int len = strlen(temp);//计算尾端位置
for (int j = 0; j < strlen(Value[index]); j++)//以队列中每个元素依次对新的键值进行拼接
{
ConnectString(temp, Value[index][j],len);
PutElemQueue(&Q, temp);//插入队列
}
}
}
}
Visit(Q);
system("pause");
return 0;
}