[力扣_17] 电话号码的字母组合

121
[ LeetCode ] [ 算法基础 ]

题目入口：点击进入

相关算法：

  • 深度优先搜索（递归回溯）——时间复杂度O(n^4),空间复杂度O(n^4)
  • 广度优先搜索（借用队列实现）——时间复杂度O(n^4),空间复杂度O(n^4)

思路和算法：

这道题是道经典的搜索题，求最多的组合，我们可以用深搜来维护每一个字符，来获取每一个解，也可以用广搜来依次拼接所有的组合。

我们采用数组来做字母映射表，根本来说，数组就是key为非负整数的hash

我们可以将题意理解成将给定的数字串”翻译“成字符串，找出所有翻译可能，翻译每一个数组都有3或4种可能。

DFS（递归回溯）

我们可以从示例知道，这和排列组合相类似吧，假设给定数字串为”23“的话，那么两重循环即可枚举出所有的解，那么输入”234“就是三重循环....

同样，我们可以用递归来实现，递归的好处就是我们不必知道他有几重循环，到达给定数字串的尾端(当扫描指针越界时)，就生成了一个解，我们则将它加入解集当中，并且结束当前递归分支（return很重要）去别的分支，直到找到所有的解

递归树如下所示：

img

从上述可以得知，我们需要所有分支全部走一遍来拼接所有可能，则我们可以用循环加递归来实现DFS

详细演示套用”王尼玛“大神图示：

img对于打印"2345"这样的字符串：
第一次递归就是上图中最下面的方格，然后处理完第一个字符2之后，将输入的字符改变成"345"并调用第二个递归函数
第二次递归处理3，将字符串改变成"45"后再次递归
第三次递归处理4，将字符串改变成"5"后继续递归
第四次递归处理5，将字符串改变成""后继续递归
最后发现字符串为空了，将结果放到列表中并返回
上面是从函数调用的角度去看的，而每次调用下一层递归时，都需要将本层的一些处理结果放到一个临时变量中，再传递给下一层，从这个变量层层传递的变化看，就像一棵树一样，这个算法的时间复杂度很高，是O(3^n)这个级别的，空间复杂度是O(n)
作者：wang_ni_ma

动图如下所示：

img

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 的结尾。最后队列中的元素就是所求结果。

图示如下：

img

img

img

img

img

img

img

img

img

img

因为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;
}

本文链接：

https://nullcode.fun/63.html
1 + 8 =
快来做第一个评论的人吧~