17.电话号码的字母组合(深度递归遍历解决经典老题)

这篇具有很好参考价值的文章主要介绍了17.电话号码的字母组合(深度递归遍历解决经典老题)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前文

C++深度递归遍历解决"电话号码的字母组合问题",本题考察的比较全面,考察到 vector的使用,深度遍历以及递归的熟练度,希望能对铁子们有所帮助

一,题目

链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

17.电话号码的字母组合(深度递归遍历解决经典老题)

二,解法

17.电话号码的字母组合(深度递归遍历解决经典老题)
如上图所示,以"256"为例,我们将三个字符串各个字符的排列组合展开,我们发现这个结构类似于多叉树的结构,主要是考察深度遍历,因此我们也可以用递归来完成。

既然已经确定可以用递归来完成,那么我们就需要确定递归所需参数。

首先我们需要创建一个 vector<string> ret用来 存储需要返回的字母组合,同时需要创建 size_t depth控制递归的深度,再创建一个 string combinestr用来 存储每组的字母组合,当然digits也是必须要传的。

所需参数已确定,那么具体的递归过程呢。

我们以上图"ajm" "ajn" "ajo"为例子,具体讲解一下递归的过程
17.电话号码的字母组合(深度递归遍历解决经典老题)

三,代码

代码实现:文章来源地址https://www.toymoban.com/news/detail-412295.html

class Solution {
    //获取每个数字对应字符串
    //由于0 1没字符,所以设置成空串
    string get_numberstr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
   void Combination(const string& digits,size_t depth,string combinestr,    vector<string>& ret)
   {    
       //depth控制深度,digits的长度就是我们递归的深度
       if(depth==digits.size())
       {
           ret.push_back(combinestr);
           return;
       }
       int digit=digits[depth]-'0';//获取数字字符
       string numberstr=get_numberstr[digit];//获取数字所对应的字符串
       for(auto ch:numberstr)
       {
           Combination(digits,depth+1,combinestr+ch,ret);

       }

   }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if(digits.size()==0)
        {
            return ret;
        }
        size_t depth=0;//控制递归深度
        string combinestr;//存储每组字符串
        Combination(digits,depth,combinestr,ret);
        return ret;
    }
};
17.电话号码的字母组合(深度递归遍历解决经典老题)
成功实现

到了这里,关于17.电话号码的字母组合(深度递归遍历解决经典老题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode 17 电话号码的字母组合

    理解题意 :         给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合                 本质上:数字代表着一个字母集合                 数字的个数决定了递归的深度,即树的深度                 数字代表的字母组合决定了当前树的宽度

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

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

    2024年02月10日
    浏览(67)
  • Day 25 | 回溯 216.组合总和III 、17.电话号码的字母组合

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

    2024年01月21日
    浏览(41)
  • Day28 17电话号码的字母组合 39组合求和 40组合求和II

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。          因为输入的数字的数量是不确定的,所以for循环的次数也是不确定的,这里就需要用到回溯的方法了。          一般回

    2024年01月16日
    浏览(47)
  • 代码随想录22| 216.组合总和III, 17.电话号码的字母组合

    题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:回溯三部曲: 1.确定函数参数:n,k,sum,startIndex; 2.结束条件,path == k,并且如果sum==n 结束递归 3.递归回溯逻辑。 题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:传入参数:输入的数字,第几个数字的

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

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

    2024年01月22日
    浏览(40)
  • leetcode:电话号码的字母组合(详解)

    给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 示例 2: 示例 3: 提示: 0 = digits.length = 4 digits[i]  是范围  [\\\'2\\\', \\\'9\\\']  的一个数字。  

    2024年02月11日
    浏览(58)
  • 【leetcode C++】电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。     . - 力扣(LeetCode) 这道题明显是需要互相匹配,如 字符串 “23”, 对应 “abc” 和 “def”。 这个

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

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

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

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

    2024年04月13日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包