【算法狂想曲】递归产生字符串(电话号码字母组合问题)

2020-03-30   111 次阅读


我又来水博客了
这次水的原因是因为5分钟内写出了执行用时和内存消耗都战胜百分百用户的一道中等题(依旧菜鸡),也是在LeetCode中第一道通过自己能力写出来的双百题(其实也没做几道)
捕获.PNG

但是显而易见这依旧是一题水题
题目如下

题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

相信大家都用过以前那种老式的固定电话,数字键上除了数字还有对应的符号与字母(我寻思这不是九键拼音么),因此现在我们需要做的就是,给定数字字符串,给出他们所有的排列组合
比如输入"23"
输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
因为2对应的字母有'abc',3对应的字母为'def',因此排列组合显而易见
但是通过程序要如何解决呢?

解题思路

很多人肯定很快就会想到,用for循环依次遍历啊,其实这个思路是对的,但需要解决的问题是,给定的字符串长度不定,如果你的字符串固定长度为3,则可以直接暴力3个for出结果,但是长度可变,这个暴力显然无法凑效
此时,递归的魅力就出来了
我们首先在函数中定义一个空字符串,然后对这个字符串使用for循环依次加上对应位置的字符,比如初始状态空字符,第一个原始字符是'2',那我们用for循环遍历就分别得到了"a","b","c"三个字符串
随后在调用函数进行递归,通过下一位原始字符进行读取,比如下一个字符是'3',那我们就得到了"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"这几个字符串,以此类推,一旦字符串长度与原始数字串长度相等,则直接扔到结果容器中,并且return终止这一条线

AC代码

class Solution {
public:
vector<string> result;
char a[9][4]={{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};                         //定义每个原始字符对应的字母
        int num[9]={0,3,3,3,3,3,4,3,4};      //定义每个原始字符对应的字母数
void perm(string yuan,string str1)           //递归函数定义
{
        
//倘若当前字符串与原始数字串长度相等,将字符串扔到容器中,返回
    if(str1.length()==yuan.length())        
    {
        result.push_back(str1);
        return;
    }
    for(int i=0;i<num[yuan[str1.length()]-'0'-1];i++)  //对原始字符对应的字母进行遍历,比如2的话就依次遍历abc
        perm(yuan,str1+a[yuan[str1.length()]-'0'-1][i]); //将当前字符串加上字母后,递归操作
}
    vector<string> letterCombinations(string digits) {
        if(!digits.length())            //应对空数字字符的坑爹情况
            return result;
         perm(digits,"");                //递归操作  
         return result;                 //返回结果
    }
};

总结

菜鸡固然是菜鸡,但是多做题还是会变成稍微有点水平的菜鸡的,递归牛逼

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议