6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)

发布时间:2023-04-20 12:00

        大家好我是Liyuyue!

        本专栏会将本博主刷题历程记录并总结下来,出成讲解的方式供给大家一起学习!

        接下来我会讲我刷的LeetCode好题用到的思路、方法分享给大家一起学习,如果大家在看的过程中还有好的方法,可以评论区或者直接找我继续讨论。

        如果大家有需要出讲解的题可以给我评论或者私聊我,我帮大家试试水~!给大家一个满意的讲解~!     

        感谢大家的支持~!


17. 电话号码的字母组合

6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)_第1张图片

class Solution {
public:
    vector letterCombinations(string digits) {

    }
};

        这道题还是有些难度的。

        这道题就是要我们对它给的digits里的数组对应九宫格里的字母进行一一对应的输出出来,但是只能输入2-9,因为位置1不是字母而是字符。

总体概述:

        通过给定的字符串中依次取出数字,通过数字找到对应的字母,然后依次一一对应,用容器存储起来,到digits(给定的字符串)取到 '\0' 也就是取完了,说明也对应的存储起来了,然后再返回。

解析:

        首先为了容易对应数字与字母的映射,我们需要创建一个数组对数字对应的字符串进行存储:

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

        但是还是有要求的,因为如果直接在类里这样写,就相当于类的成员变量,这里的 = 不是赋值,而是给的缺省值:

class Solution {
public:
    string count_str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector letterCombinations(string digits) {

    }
};

        所以不能这么写,可以给成static静态的,但是静态的必须要在类外面初始化,那不如直接给成全局的,直接在外面定义就可以:

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

class Solution {
public:
    vector letterCombinations(string digits) {

    }
};

        其实通过上面的总体概括,我们就应该能感觉到这里用递归来写会方便很多,因为是多个字符串一一组合,而递归正可以做这种事情:

6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)_第2张图片

         当在遍历ad的时候,遍历到z的时候返回到第二层,然后继续遍历第二层,遍历第二层第二个字母的时候再向下进行依次遍历......

6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)_第3张图片

         既然我们确定了要用递归来解决这个问题,那么我们就要想如何写递归条件

重点:

        我们要定义一个变量,用来记录递归了几层(深度),也就是判断digits中的字符串取没取完。然后定义一个vector容器进行对stringd类(字符串)进行存储,还要定义一个string用来对字符串递归的时候进行传递。

        这里进行传递的意思是:第一次记录了a,然后将a传递到下一层,记录ad,然后将ad传递到下一层,记录adw,因为这是最后一层,然后继续记录adx、ady、adz,记录完了,返回到第二层。所以这时我们就要注意了,我们用string进行传递的时候,不能传引用,因为我们的目的是让第二层只传递的是第一层是字母,如果第三层的改变影响从第一层传给第二层的字母,那就达不成我们想要的结果了

        递归的条件说完了,继续说说递归结束的条件因为我们定义了一个记录深度的变量,当深度达到最后一层,也就是到了 数字映射的字符串string的字符个数就结束此递归,但是结束之前要将用来记录的string里的字符串加载到vector这个容器中,然后再返回

6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)_第4张图片

        最后要注意的就是如果穿过来的为空,直接返回一个空串就可以了

        这下思路就讲完了,大家可以尝试写一写,其实写起来很简单,但是思路不是很好想到,各种对数据进行存储和传递。

        相信经过讲解,大家也对这个思路很清晰了,大家如果还没理解清楚,一定要记住我设置的那些变量,然后画递归图,一步步分析,只有了解了递归的方式和递归的路程,才能真正明白是怎么进行的递归。

代码展示:

        我对下面的代码进行了注释。

        这里有的人喜欢对str用传引用,如果只是传引用的话是不对的,因为string& str这个形参是通过str + ch 这个实参传递的,这个实参是临时变量,要想使用传引用,必须要const string& str,这样才可以,因为const会延长临时变量的生命周期。

        所以我不推荐用,因为其实string str 和 const string& str 在效率上是一样的,编译器会给string str优化,因为传来的是str + ch,会创建一个临时变量进行构造,然后传给形参再拷贝构造,编译器会直接优化为直接拷贝构造,所以是一样的!

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

class Solution {
public:
     void _letterCombinations(const string& digits,int i, string str, vector& ret)
    // void _letterCombinations(const string& digits,int i, const string& str, vector& ret)
    { // 建议使用第一个(没注释掉的)
        if(digits.size() == i) // 递归结束条件
        {
            ret.push_back(str);
            return;
        }
        int num = digits[i] - '0'; // 将字符转换为数字
        const string& letters = count_str[num];
        for(auto ch : letters)
            _letterCombinations(digits, i + 1, str + ch, ret); // 进行递归
    }
    vector letterCombinations(string digits) {
        vector ret; // 用来存储的容器
        if(digits.empty()) // 看是不是为空
            return ret;
        int i = 0;
        string s; // 用来递归的字符串
        _letterCombinations(digits, i, s, ret);
        return ret;
    }
};

6.【刷爆LeetCode】电话号码的字母组合(多方法、多思路)_第5张图片

        如上就是 电话号码的字母组合 的解析,接下来本专辑会持续更新【刷爆LeetCode】,和大家一起爆扣LeetCode!!!,如果大家喜欢看此文章并且有收获,可以时刻关注我,本专栏持续更新!

        感谢大家观看,感谢大家支持!

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号