电话号码的字母组合

题目：17. 电话号码的字母组合 - 力扣（Leetcode）

思路：

给定一个电话号码字符串 digits，须输出它所能表示的所有字母组合。我们可以先定义一个数字字符到字母表的映射表 numToStr，然后再用 Combine 函数递归地去尝试构造出每一个可能的字母组合。当已经处理完已知的所有数字时（即 di == digits.size()），就可以将当前已经组合好的字符序列 combineStr 加入到结果列表 retV 中。

具体递归过程的实现如下：首先获取当前要处理的数字编号 num，从映射表中取出该数字对应的所有字符 str，并遍历该字符集中的每一个字符 ch：将 ch 这个字符追加到当前的字符序列 combineStr 中，然后继续往下一层递归；在这个新的递归中，di 的值加一，以便能够继续处理下一个数字。直到我们处理完所有的数字并递归返回到最初的调用点结束整个递归过程为止。

注意上述递归过程中，临时字符串 combineStr 是通过每次添加新字符而累积的，因此需要在递归返回时进行回退，以保证下一轮试探可以得到正确的结果。

代码实现：

class Solution 
{//定义数字字符到字母表的映射表string numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//或者：char* numToStr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:void Combine(string digits, int di, vector<string>& retV, string combineStr) {//递归结束标志：已经处理完所有的数字，将当前字母串加入结果列表if(di == digits.size()) {retV.push_back(combineStr);return;}//获取当前要处理的数字编号及其对应的字母串int num = digits[di] - '0';string str = numToStr[num];for(auto ch: str) {//往下一层搜索找到新的字母字符并加入当前字母串Combine(digits, di+1, retV, combineStr+ch);} }vector<string> letterCombinations(string digits) {vector<string> v;//单独处理空字符串的情况if(digits.empty()) {return v;}//递归生成所有可能的字母组合string str;Combine(digits, 0, v, str);return v;}
};

解释:

这段代码主要实现了一个递归回溯法，用于求解电话号码的字母组合问题。下面是它的详细解释：

• 第1步：定义类Solution和一个私有函数Combine以及一个公有函数letterCombinations

• 第2步：定义数字字符到字母表的映射表numToStr，其中第一个条目对应的是数字 0。这里使用字符串数组来存储映射字符。

• 第3步：定义回溯函数Combine，它有4个参数：当前正在处理的电话号码（digits）、当前处理到的数字位置（di）、结果列表容器（retV）和已经处理好的字母组合串（combineStr）。

• 第4步：在Combine中，当要处理的数字位置 di 达到了 digits 的长度时，即表明已经完成了一次字母组合的构造。此时将之前收集到的正确字母组合串追加到结果列表retV 中，并直接退出该递归过程。

• 第5步：当递归搜索还未结束时，从当前数字位置开始（di 所指的位置），获取该位置上的数字编号 num，并找到对应的字母串 str。然后遍历该字符集中的每一个字符 ch，在 combineStr 后添加该字符，也就是生成了一个新的临时字母组合串，形如 combineStr+ch。

• 第6步：新的临时字母组合串（即combineStr+ch）被传入到下一层搜索中，以便用于试探下一个数字所对应的所有可能字母。

• 第7步：最终、递归地从 combineStr 开始往后连接新的字符，直到整个字符串构造完成。Combine 函数的返回值表示所有可能的字母组合串，以向上递归给调用函数传递答案。

• 第8步：letterCombinations 外部函数中，为效率考虑先对空字符串进行特判；然后用 Combine 函数生成所有可能的字母组合排列，并返回结果容器 retV。