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

这篇具有很好参考价值的文章主要介绍了【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

📖题目描述
【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合,C语言练习,c语言,c++,算法,回溯

题目出处:电话号码的字母组合
示例:
【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合,C语言练习,c语言,c++,算法,回溯
📖题解
 这是一道典型的排列组合问题,根据输入,我们需要找到所有的组合。下面以输入字符串digits = "23"为例来讲解这道题目。
图解:
【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合,C语言练习,c语言,c++,算法,回溯
分析:
 首先要知道输入的字符串"23"中的数字字符分别对应哪些字符串,其中2对应字符串"abc",3对应字符串"def"。接下来就该对这两个字符串中的字符进行排列组合,一共有 3 × 3 = 9 3×3=9 3×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;
    }
};

 今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,您的支持就是春人前进的动力!
【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合,C语言练习,c语言,c++,算法,回溯文章来源地址https://www.toymoban.com/news/detail-561398.html

到了这里,关于【C/C++练习】经典的排列组合问题(回溯算法)——电话号码的字母组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Day 25 | 回溯 216.组合总和III 、17.电话号码的字母组合

    题目 文章讲解 视频讲解 思路: 以回溯函数做对称,上面做了什么操作,下面也是 题目 文章讲解 视频讲解 思路:思路上和组合很像,不同的是对字符串进行操作 还得再想想

    2024年01月21日
    浏览(41)
  • 代码随想录阅读笔记-回溯【电话号码的字母组合】

    题目 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入:\\\"23\\\" 输出:[\\\"ad\\\", \\\"ae\\\", \\\"af\\\", \\\"bd\\\", \\\"be\\\", \\\"bf\\\", \\\"cd\\\", \\\"ce\\\", \\\"cf\\\"]. 说明:尽管上面的答案是按字典序排列的,但是你可以任意

    2024年04月13日
    浏览(52)
  • 17.电话号码的字母组合(深度递归遍历解决经典老题)

    C++深度递归遍历解决\\\"电话号码的字母组合问题\\\",本题考察的比较全面,考察到 vector的使用,深度遍历以及递归的熟练度 ,希望能对铁子们有所帮助 链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/ 如上图所示,以\\\"256\\\"为例,我们将三个字符串各个字符的排列组合展

    2023年04月13日
    浏览(41)
  • LeetCode 1079. Letter Tile Possibilities【哈希表,回溯,动态规划,排列组合】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月10日
    浏览(50)
  • 代码随想录Day20 回溯算法 LeetCode77 组合问题

    以下内容更详细解释来自于:代码随想录 (programmercarl.com) 回溯法也叫回溯搜索法,是搜索法的一种,我们之前在二叉树中也经常使用到回溯来解决问题,其实 有递归就有回溯 ,有的时候回溯隐藏在递归之下,我们不容易发觉,今天我们来详细介绍一下什么是回溯,它能解决哪些问题.

    2024年02月08日
    浏览(50)
  • 电话号码的字母组合-算法

    按电话上数字与字母的对应关系,如2={a,b,c},3={d,e,f}等,给定一串数字如267,则求出abc,mno,qprs的所有组合,如amq,amp...cor,cos等 遍历都可以用回溯的方式尝试解决,每次遍历结束后,将上一层元素删除,满足长度,则加入到结果中      

    2024年01月22日
    浏览(40)
  • 【算法Hot100系列】电话号码的字母组合

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月01日
    浏览(39)
  • 递归算法学习——电话号码的字母组成,括号生成,组合

    目录 一,电话号码的字母组合 1.题意 2.例子 3.题目接口  4.解题代码和思路 代码: 思路: 二,括号的生成 1.题意 2.例子 3.题目接口 四,解题代码和思路 1.先写代码: 2.思路 三,组合 1.题意 2.例子 3.题目接口 4.解题代码 1.题意 给定一个仅包含数字  2-9  的字符串,返回所有

    2024年02月10日
    浏览(67)
  • 力扣第40题 组合总和 || c++ 回溯经典

    40. 组合总和 II 中等 相关标签 数组   回溯 给定一个候选人编号的集合  candidates  和一个目标数  target  ,找出  candidates  中所有可以使数字和为  target  的组合。 candidates  中的每个数字在每个组合中只能使用  一次  。 注意: 解集不能包含重复的组合。  示例 1: 示例

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包