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

前文

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

一，题目

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

二，解法

如上图所示，以"256"为例，我们将三个字符串各个字符的排列组合展开，我们发现这个结构类似于多叉树的结构，主要是考察深度遍历，因此我们也可以用递归来完成。

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

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

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

我们以上图"ajm" "ajn" "ajo"为例子，具体讲解一下递归的过程

三，代码

代码实现:

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;}
};

成功实现