【17. 电话号码的字母组合 中等】

题目：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

---

思路：

数字和字母如何映射

首先要解决的问题是数字和字母如何映射，可以使用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”，抽象为树形结构，如图所示：

图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

回溯三部曲：

• 确定回溯函数参数

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

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

注意这个index可不是77.组合 中等中的startIndex了。

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

代码如下：

vector<string> result;
string path;
void backtracking(const string& digits, int index)

• 确定终止条件

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

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

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

代码如下：

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

• 确定单层遍历逻辑

首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。

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

int digit = digits[index] - '0';    // 将index指向的数字转为int
string letters = letterMap[digit];  // 取数字对应的字符集
for(int i = 0; i < letters.size(); i++){path.push_back(letters[i]); //  处理backtracking(digits, index + 1);    //  递归path.pop_back();    //  回溯
}

注意这里for循环，可不像是在回溯算法：求组合问题77.组合 中等中从startIndex开始遍历的。

因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77.组合 中等是求同一个集合中的组合！

---

代码：

class Solution {
public://  数字和字母映射const string letterMap[10] = {"", //  0"", //  1"abc",  //  2"def",  //  3"ghi",  //  4"jkl",  //  5"mno",  //  6"pqrs", //  7"tuv",  //  8"wxyz"  //  9};vector<string> result;string path;//  charMap为当前数字对应的字母字符串void backtracking(const string& digits, int index){if(digits.size() == 0) return;if(index == digits.size()){result.push_back(path);return;}int digit = digits[index] - '0';    // 将index指向的数字转为intstring letters = letterMap[digit];  // 取数字对应的字符集for(int i = 0; i < letters.size(); i++){path.push_back(letters[i]); //  处理backtracking(digits, index + 1);    //  递归path.pop_back();    //  回溯}}vector<string> letterCombinations(string digits) {backtracking(digits, 0);return result;}
};

---

总结：

时间复杂度: O(3^m * 4^n)，其中 m 是对应三个字母的数字个数，n 是对应四个字母的数字个数
空间复杂度: O(3^m * 4^n)

本并重点强调了和前面讲解过的77.组合 中等的区别，本题是多个集合求组合，所以在回溯的搜索过程中，都有一些细节需要注意的。

---

参考：

代码随想录