[力扣_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;
}