电话号码的字母组合【C++】【力扣刷题】

解题思路：

以第一个为例,digits = “23”，表明从电话号码的按键中选取2和3这两个字符，然后去寻找它们各自所对应的字母，这里每一个数字字符所对应的字母的不同，0对应的是空字符，而1的话题目中讲到是不对应任何字母，要注意的是像7和9所对应的是4个字母。
以上这些应该用一个数组或者容器将它们存起来。
这里由于digits的个数是不确定的，所以我们没有办法使用多层for循环来嵌套求解。就需要用到递归，回溯的方式来解题。
那么不难想象，这题应该是多叉树的递归并且保存数据到vector<string>容器中。

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

解题步骤：

1.看题，传入一个string类的digits对象，里面是字符串. 返回值是vector<string>

所以我们应该创建一个vector<string>容器的对象 vector<string> statistics；

2.我们需要把对应的关系映射到一维数组中，放到函数外面。

class Solution {
public:const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" vector<string> letterCombinations(string digits){vector<string> statistics;//解题过程return statistics;}
};

3.我们需要写一个子函数来完成递归操作。那我们需要传什么参数呢?

①我们需要传接收型参数vector<string> statistics;

②需要传digits，来获取需要的字符

③需要传一个n，来计算深度

④我们还需要能够保存字符串的string类对象

class Solution {
public:const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };void _letterCombinations(vector<string>& statistics, string str, int n, string& digits){}vector<string> letterCombinations(string digits){vector<string> statistics;string str;_letterCombinations(statistics, str, 0, digits);return statistics;}
};

4. 我们需要写一个递归的返回条件

当到了最深的层次时，先把字符串push_back到vector的容器中，然后回溯。

if (n == digits.size()){statistics.push_back(str);Static++;return;}

5.写执行过程：

int sz = digits[n] - 48;
string s1;
s1 = numStrArr[sz];
for (int i = 0; i < s1.size(); i++)
{char ch = s1[i];_letterCombinations(statistics, str + ch, n + 1, digits);
}

过程

1. sz记录数字，为了通过下标来映射字符串。

2. 把字符串存储到string类里面，方便访问字符，ch=s1[i]，记录字符

3. 递归

我们为什么是采用+号，而不是+=呢？

        第一遍adg，然后存到vector<string> statistics对象中
        之后退到上一层，str=="ad"，n==2，再递归，把adh存储起来。
        依次进行。

6.还差最后一步：

有一个测试用例是我们就不能进入子函数。

vector<string> letterCombinations(string digits){vector<string> statistics;if(digits.size()==0) return statistics;//如果为空，就不进入子函数string str;_letterCombinations(statistics, str, 0, digits);return statistics;}

6.完整的代码：

class Solution {
public:const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };void _letterCombinations(vector<string>& statistics, string str, int n, string& digits){if (n == digits.size()){statistics.push_back(str);return;}int sz = digits[n] - 48;string s1;s1 = numStrArr[sz];for (int i = 0; i < s1.size(); i++){char ch = s1[i];_letterCombinations(statistics, str + ch, n + 1, digits);}}vector<string> letterCombinations(string digits){vector<string> statistics;if(digits.size()==0) return statistics;string str;_letterCombinations(statistics, str, 0, digits);return statistics;}
};