17.电话号码的字母组合

╰+哭是因爲堅強的太久メ 2023-10-16 12:53 16阅读 0赞

#### 17.电话号码的字母组合 ####

*  题干描述
 *  解题思路
 *   *  1. 数字和字母如何映射
     *  2. 回溯法来解决n个for循环的问题
     *   *  回溯三部曲
         *   *  2.1 确定回溯函数参数
             *  2.2 确定终止条件
             *  2.3 确定单层遍历逻辑
     *  3. 输入1\*\#按键等等异常情况
 *  总结
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。  
![在这里插入图片描述][174b8db5305443c7baf75f35a6bb42ac.png]  
示例:

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

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

## 解题思路 ##

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

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

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

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

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

### 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
    };

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

例如：输入：“23”，抽象为树形结构，如图所示：  
![在这里插入图片描述][06279a329f254723bbeaa5faad59163e.png]  
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出\[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”\]。

#### 回溯三部曲 ####

##### 2.1 确定回溯函数参数 #####

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

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

注意这个index可不是 **77.组合** 和 **216.组合总和III** 中的startIndex了。

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

##### 2.2 确定终止条件 #####

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

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

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

代码如下：

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

##### 2.3 确定单层遍历逻辑 #####

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

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

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(); // 回溯
    }

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

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

### 3. 输入1\*\#按键等等异常情况 ###

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

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

将回溯藏在递归的参数里的写法很不直观，不建议使用。

## 总结 ##

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

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

## 代码实现 ##

class Solution {
        
        // 17.电话号码的字母组合
        // 设置全局列表存储最后的结果
        List<String> list = new ArrayList<>();
    
        public List<String> letterCombinations(String digits){
        
            if(digits == null || digits.length() == 0){
        
                return list;
            }
            // 初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串
            String[] numString = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            // 迭代处理
            backTracking(digits, numString, 0);
            return list;
        }
    
        // 每次迭代获取一个字符串，所以会涉及大量的字符串拼接, 所以这里选择更为高效的StringBuilder
        StringBuilder temp = new StringBuilder();
    
        // 比如digits如果为"23", num为0, 则str表示2对应的abc
        public void backTracking(String digits, String[] numString, int num){
        
            // 遍历全部一次记录一次得到的字符串
            if(num == digits.length()){
        
                list.add(temp.toString());
                return;
            }
            // str表示当前num对应的字符串
            String str = numString[digits.charAt(num) - '0'];
            for(int i = 0; i < str.length(); i++){
        
                temp.append(str.charAt(i));
                //c
                backTracking(digits, numString, num+1);
                //剔除末尾的继续尝试
                temp.deleteCharAt(temp.length() - 1);
            }
    
        }
    }

**参考资料**：[代码随想录-17.电话号码的字母组合][-17.]

[Link 1]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
[174b8db5305443c7baf75f35a6bb42ac.png]: https://img-blog.csdnimg.cn/174b8db5305443c7baf75f35a6bb42ac.png
[06279a329f254723bbeaa5faad59163e.png]: https://img-blog.csdnimg.cn/06279a329f254723bbeaa5faad59163e.png
[-17.]: https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE