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

1. 题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同），注意 1 不对应任何字母：

2. 示例

示例1：

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

 示例2：

输入：digits = ""
输出：[]

 示例3：

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

3. 分析

（1）需要用一个数组建立数字和字符串的映射，这个数组不会变化，不要放在类里面，否则每个对象都会包含这个数组，写成全局的

（2）由于要组合，所以要依次取digit里面的数字，拿其对应的字母分别组合，可以采用递归

原代码： 

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

    }
};

 要求返回值是vector<string>的，返回值为ret，传参是digits，为了依次拿到digit里面的每个数字的值，可以用递归来实现一层一层组合，在这里递归就有层数传参，原生代码给的入参不够用，重新写一个递归函数，入参有数字digits，层数i，还有ret。

digits的长度是几，就递归几层，如digits为236，长度是3，就递归3层：

（1）i为0时，就是第1层，数字2对应字母abc，再用循环取第1个字母a，进行组合

（2）组合对象是3对应的字母，这时i需要++变成1才能到第2层，即数字3对应的字母def，循环取第1个字母d

（3）递归第3层，i++变成了2，数字6对应的字母是mno，循环取第1个字母m

每层挑一个字母进行组合，递归到最后一层，就得到了字母组合，将最后一层循环完毕，再继续循环第2层，再去组合第3层，直到第2层组合完毕，这才组合完了第1层第1个字母，再循环第一层，直到组合完第1层的所有字母，就组合出了所有的结果：

 （3）如果递归到最后一层结束，就将字符串组合结果放入到结果数组中

4. 代码实现

//全局变量，一直不变
string num_str[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };

class Solution {
public:
    void _letterCombinations(const string& digits, size_t i, string str,vector<string>& ret)
    {
        //递归到最后一层，就组合成功了一个字符串，放到结果数组中
        if(i == digits.size())
        {
            ret.push_back(str);
            return;
        }
        int num = digits[i] - '0';
        const string& letters = num_str[num];//不需要深拷贝，只需要浅拷贝，所以加&

        //digits中的第i个数字对应的字符串，根据字符串中字符的个数迭代
        for(auto ch:letters)
        {
            _letterCombinations(digits,i+1,str+ch,ret);//str+ch是正在组合中的字符串
        }
    }

    vector<string> letterCombinations(string digits)
    {
        vector<string> ret;//组合的字符串结果数组

        //判空
        if(digits.empty())
        {
            return ret;
        }

        int i = 0;
        string s;//每个组合的字符串
        _letterCombinations(digits, i, s,ret);//递归组合
        return ret;
    }
};

递归调用过程：只画了以ad为前缀的字母组合调用过程，其他的都类似