回溯算法：电话号码的字母组合

标签：测试   版本   面试   如图所示   长度   二维   ado   src   没有   

通知：我已经将公众号文章和学习相关的资料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在电脑上学习，可以fork到自己仓库，顺便也给个star支持一波吧！

?
17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

17.电话号码的字母组合
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路
从示例上来说，输入"23"，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。

如果输入"233"呢，那么就三层for循环，如果"2333"呢，就四层for循环.......

大家应该感觉出和回溯算法：求组合问题！遇到的一样的问题，就是这for循环的层数如何写出来，此时又是回溯法登场的时候了。

理解本题后，要解决如下三个问题：

1. 数字和字母如何映射
2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
3. 输入1 * #按键等等异常情况
   数字和字母如何映射
   可以使用map或者定义一个二位数组，例如：string letterMap[10]，来做映射，我这里定义一个二维数组，代码如下：

const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};

**回溯法来解决n个for循环的问题**
对于回溯法还不了解的同学看这篇：关于回溯算法，你该了解这些！

例如：输入："23"，抽象为树形结构，如图所示：

![](https://s4.51cto.com/images/blog/202012/28/05c0cebc0c6604336b5aa51799b7b85f.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=)
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

回溯三部曲：

* 确定回溯函数参数
首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。

再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。

注意这个index可不是 回溯算法：求组合问题！和回溯算法：求组合总和！中的startIndex了。

这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。

代码如下：

vector result;
string s;
void backtracking(const string& digits, int index)

* 确定终止条件
例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。

那么终止条件就是如果index 等于 输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。

然后收集结果，结束本层递归。

代码如下：

if (index == digits.size()) {
result.push_back(s);
return;
}

1. 确定单层遍历逻辑
首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

然后for循环来处理这个字符集，代码如下：

int digit = digits[index] - ‘0‘; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back(); // 回溯
}

**「注意这里for循环，可不像是在回溯算法：求组合问题！和回溯算法：求组合总和！中从startIndex开始遍历的」**。

**「因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III都是是求同一个集合中的组合！」**

**输入1 * #按键等等异常情况**
代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。

「但是要知道会有这些异常，如果是现场面试中，一定要考虑到！」

**C++代码**
关键地方都讲完了，按照关于回溯算法，你该了解这些！中的回溯法模板，不难写出如下C++代码：

// 版本一
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector result;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - ‘0‘; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back(); // 回溯
}
}
vector letterCombinations(string digits) {
s.clear();
result.clear();
if (digits.size() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
};

一些写法，是把回溯的过程放在递归函数里了，例如如下代码，我可以写成这样：（注意注释中不一样的地方）

// 版本二
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector result;
void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - ‘0‘;
string letters = letterMap[digit];
for (int i = 0; i getCombinations(digits, index + 1, s + letters[i]); // 注意这里的不同
}
}
vector letterCombinations(string digits) {
result.clear();
if (digits.size() == 0) {
return result;
}
getCombinations(digits, 0, "");
return result;

}

};

我不建议把回溯藏在递归的参数里这种写法，很不直观，我在二叉树：以为使用了递归，其实还隐藏着回溯这篇文章中也深度分析了，回溯隐藏在了哪里。

所以大家可以按照版本一来写就可以了。

**总结**
本篇将题目的三个要点一一列出，并重点强调了和前面讲解过的77. 组合和216.组合总和III的区别，本题是多个集合求组合，所以在回溯的搜索过程中，都有一些细节需要注意的。

其实本题不算难，但也处处是细节，大家还要自己亲自动手写一写。

**「就酱，如果学到了，就帮Carl转发一波吧，让更多小伙伴知道这里！」**

回溯算法：电话号码的字母组合

标签：测试   版本   面试   如图所示   长度   二维   ado   src   没有   

原文地址：https://blog.51cto.com/15069438/2576394