代码随想录二刷｜回溯｜电话号码的字母组合

题目描述
解题思路
- 数字和字母如何映射
- 回溯法来解决n个for循环的问题
代码实现

题目描述

17，电话号码的字母组合

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

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

在这里插入图片描述

示例:

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

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

解题思路

本题要解决如下三个问题：

数字和字母如何映射
两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
输入1 * #按键等等异常情况

数字和字母如何映射

可以定义一个二维数组,代码如下：

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

回溯法来解决n个for循环的问题

遍历的深度是输入的字符串的长度，而叶子节点就是我们要收集的结果。

回溯三部曲：

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

参数有题目中给的string digits，然后还要有一个int型的index。这个index用来记录遍历到第几个数字了，也就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。
```
vector<string> result;
string s;
void backtracking(const string& digits, int index)
```
确定回溯函数的终止条件
如果index 等于输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。然后就可以收集结果，结束本层递归。
```
if (index == digits.size()) {
	result.push_back(s);
	return;
}
```

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

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

int digit = digits[index] - '0';
string letters = letterMap[digit];
for (int i = 0; i < letters.size(); i++) {
	s.push_back(letters[i]);
	backtracking(digits, index + 1);
	s.pop_back();
}

代码实现

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<string> 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 < letters.size(); i++) {
            s.push_back(letters[i]);            // 处理
            backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了
            s.pop_back();                       // 回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};