【LeetCode】【电话号码的字母组合】

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

 

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

如果使用递归的话可以考虑深度优先遍历 

class Solution {
    //创建数字和字符映射
    const char* numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    // string numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
//dights为输入的数据，也就是电话机上按下的数字，然后di表示的是我们当前处理的是dighits中的哪一位
//combinestr是我们每一次枚举的临时结果，reV是我们的汇总的结果。
    void combine(string digits,int di,vector<string>& retV,string combineStr)
    {
        //当每一层都完成了之后，就将结果加到我们的retV中
        if(di==digits.size())
        {
            retV.push_back(combineStr);
            return ;
        }
//取数字字符映射的字符串
        int num=digits[di]-'0';
//取出数字对应的字符
        string str=numToStr[num];
        //遍历数字对应的字符中的每一个字符
        for(auto ch: str)
        {
            //将我们当前层取到的字符往下一层传递
//这个combineStr+ch是不会对combineStr产生影响的，
//所以在下一次遍历的时候不用把当前的这个位置的字符擦除。
            combine(digits,di+1,retV,combineStr+ch);
        }
    }
    vector<string> letterCombinations(string digits) {
        //v作为我们最终返回的结果
        vector<string> v;
//如果传给我们的数据是空的话，就直接返回空的v
        if(digits.empty())
        {
            return v;
        }
        string str;
        combine(digits,0,v,str);

        return v;
    }
};

本题与下面这道题的最后一种写法的思路（递归）相似【LeetCode】【剑指offer】【打印从1到最大的n位数】_桜キャンドル淵的博客-CSDN博客