【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

简介: 【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合

b04f4b4a78af42acbb3e53adc662fe9a.gif📖题目描述


b365e4ace25341ee810f1fbc05ac22c1.png

题目出处电话号码的字母组合

示例:

f59e4125bd70416f935c04fa24f7d2d8.png

📖题解

 这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串digits = "23"为例来讲解这道题目。

图解:

6b10978347a94538ae95446a57542d73.png

分析:

 首先要知道输入的字符串"23"中的数字字符分别对应哪些字符串,其中2对应字符串"abc",3对应字符串"def"。接下来就该对这两个字符串中的字符进行排列组合,一共有3 × 3 = 9 3×3=93×3=9种组合,答案很简单,难点在于如何有规律的选取出所有的结果,其实只需要把我们的选取过程转化成代码即可。选取过程如上图所示,先要纵向去遍历,一般这种也叫DFS(深度优先遍历),接着横向去遍历,其中纵向遍历要在不同的集合中选取元素,需要借助递归来实现,横向遍历是针对一个集合的,所以可以借助for循环来实现。下面将结合代码来展示具体的选取过程。

建立映射关系:

 首先需要建立起2-9数字字符所对应的字符串,我们可以通过数组来实现,利用数组下标的对应关系,一个下标对应一个字符串,2-9就可以当作是数组的下标,但当前输入的是一个字符串,因此会涉及到将一个字符串中的数字字符转换成数字。

string arr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

开始选取:

 选取过程的代码需要考虑以下三个点:

确定递归函数所需的参数

递归的终止条件

单层遍历的逻辑

确定递归函数所需的参数:

 首先需要一个字符串s来收集每一次选取到的字符,当遇到终止条件,s收集到的所以字符九就是一个结果,我们要把这个结果存储起来,因此还需要一个字符串数组res来存储选取结果,其次我们需要知道当前要在哪个字符串中选取字符,为此还需要两个参数,一个是题目中的输入参数digits,只知道它是不够的,例如:通过digits = "23"我们只能知道要在"abc"和"def"两个字符串中选取,但是for循环是对一个字符串进行遍历,在一个字符串中选取,因此我们还需要传递一个参数来确定具体是在哪个字符串中选取。可以传一个size_t类型的index,用来表示digits字符串的下标,因为有了下标就可以唯一确定字符串中的一个数字字符,而一个数字字符就对应一个字符串。

 void Combinations(string s, vector<string>& res, string& digits, size_t index)

注意,并没有把s设置成引用变量,这里的目的是,每收集到一个字符,加把他加到s字符串上,如果s是一个引用,s就始终表示同一块空间,那在找到一个结果,存储起来后,要把s重置才能进行下一个结果的查找。相反res是一个引用,因为可以把每次选出来的结果往同一块空间加,无需每次开空间,digits也同理,是否用引用要根据实际情况来定,不能一概而论。

递归的终止条件:

 递归结束,意味着选取出了一个结果,那递归的终止条件,就可以理解成,选取出一个结果的条件,还是以digits = "23"为例:选取出一个结果,即在"abc"和"def"两个字符串中各选取一个字符,此时出结果了,递归也应该结束了。如何知道在所有字符串中都选取了一个字符呢?还记得参数index嘛?它用来具体确定在哪个字符串中选组,这里只要在字符串def中选取之后,就可以得出一个结果,递归也就结束了。

if(index == digits.size())//此时说明已经在每个字符串中都选取了一个字符
{
  res.push_back(s);//把结果存入结果集中
  return;
}

单层遍历的逻辑:

 首先要知道知道当前遍历的是哪一个字符串,这需要通过第一步的映射关系得到,接着遍历得到一个字符后,把它加入到s中,然后通过递归,去下一个集合选取字符。

int i = digits[index] - '0';//把字符数字转换成普通数字
string str = arr[i];//根据映射关系找到,当前层要遍历的字符串
for(size_t i = 0; i < str.size(); i++)//遍历当前层的字符串
{
  Combinations(s + str[i], res, digits, index + 1);//获取到一个字符后,去下一个字符串获取下一个字符
  //s + str[i]:把戒指目前收集到的字符全传给下一层
  //res:结果集
  //index + 1:到下一个字符串中去获取字符
}

完整代码展示:

class Solution {
    string arr[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    void Combinations(string s, vector<string>& res, string& digits, size_t index)
    {
        if(index == digits.size())//此时说明已经在每个字符串中都选取了一个字符
        {
          res.push_back(s);//把结果存入结果集中
          return;
        }
        int i = digits[index] - '0';
        string str = arr[i];
        for(size_t i = 0; i < str.size(); i++)
        {
            Combinations(s + str[i], res, digits, index + 1);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> res;//定义结果集
        if(digits.size() == 0)//输入一个空串,直接返回
        {
            return res;
        }
        string str;
        Combinations("", res, digits, 0);
        //"":表示目前什么结果也没收集到
        //0:从digits的第一个数组字符所对应的字符串开始搜索
        return res;
    }
};

 今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,您的支持就是春人前进的动力!

目录
相关文章
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
20天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
20天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
20天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
461 0
高精度算法(加、减、乘、除,使用c++实现)
|
20天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!