17. 电话号码的字母组合

朴灿烈づ我的快乐病毒、 2023-01-03 06:00 99阅读 0赞

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

## 1、题目要求 ##

> **题目描述**

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

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

![image-20201231141528182][]

> **示例**

**示例1：**

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

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

## 2、代码思路 ##

> **1、深度优先（递归求解）**

但凡需要列举出所有结果的题目，立即推：递归搜索

**思路**：假设我们需要求解数字序列 `"23456"` 对应的字母组合，`'2'` 对应的字符为 `'a'`、`'b'`、`'c'`，分别将这三个字母与 `"3456"` 对应的字母组合进行组合即可，以此类推得到递归的思路

**关键点**：定义 `path` 变量记录当前递归的路径，往深层递归时进行 `append()` 操作，回溯时进行 `delete()` 操作

--------------------

**举个栗子：`"23"` 的递归求解过程**

![image-20210107182830901][]

> **2、广度优先（队列求解）**

如果你愿意一层一层一层地剥开我的心

![image-20210107190713442][]

## 3、代码实现 ##

> **1、深度优先（递归求解）**

class Solution {
        
        private List<String> res = new ArrayList<>();
        Map<Character, String> phoneMap = new HashMap<Character, String>() {
        {
        
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
    
        public List<String> letterCombinations(String digits) {
        
            // Guard Safe
            if (digits == null || digits.length() == 0) {
        
                return res;
            }
            // 递归求解所有字母组合
            recursionCalcletterCombinations(digits, new StringBuilder());
            // 返回结果
            return res;
        }
    
        /**
         * @description: 递归求解字符串对应的所有字母组合
         * @param: digits   剩余的字符串
         * @param: path     已经求解的字母路径
         * @return: void
         * @author Oneby
         * @date: 17:19 2021/1/7
         */
        public void recursionCalcletterCombinations(String digits, StringBuilder path) {
        
            // 当 digits 的长度为 0 时，表示当前路径已经到头
            if (digits.length() == 0) {
        
                // 将当前路径添加到结果中，然后开始回溯寻找其他路径
                res.add(path.toString());
                return;
            }
            // 获取当前数字对应的字母序列
            String charSeq = phoneMap.get(digits.charAt(0));
            for (int j = 0; j < charSeq.length(); j++) {
        
                // 将字符添加到路径中
                path.append(charSeq.charAt(j));
                // 继续下一步的搜素
                recursionCalcletterCombinations(digits.substring(1, digits.length()), path);
                // 回溯后恢复现场
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

> **2、广度优先（队列求解）**

class Solution {
        
        private List<String> res = new ArrayList<>();
        Map<Character, String> phoneMap = new HashMap<Character, String>() {
        {
        
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
    
        public List<String> letterCombinations(String digits) {
        
            // Guard Safe
            if (digits == null || digits.length() == 0) {
        
                return res;
            }
            // 添加第一个字符对应的字母组合
            int index = 0;
            Queue<String> queue = new LinkedList<>();
            String charSeq = phoneMap.get(digits.charAt(index++));
            for (int i = 0; i < charSeq.length(); i++) {
        
                queue.add(charSeq.substring(i, i + 1));
            }
    
            // 依次遍历字符串中每一个数字
            while (index < digits.length()) {
        
                // 遍历到 index 索引处，字符组合的个数
                int size = queue.size();
                // 队列中的每一个字符组合 + 当前数字对应的字符
                for (int i = 0; i < size; i++) {
        
                    String queueHead = queue.remove();
                    charSeq = phoneMap.get(digits.charAt(index));
                    for (int j = 0; j < charSeq.length(); j++) {
        
                        queue.add(queueHead + charSeq.charAt(j));
                    }
                }
                index++;
            }
    
            // 返回结果
            while (queue.isEmpty() == false){
        
                res.add(queue.remove());
            }
            return res;
        }
    }

[17.]: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
[image-20201231141528182]: /images/20221119/4c2763ea3879424aa923721435c50087.png
[image-20210107182830901]: /images/20221119/d912a67c8d734d0fbfe11a8966fb6f10.png
[image-20210107190713442]: /images/20221119/4035f209f64a40f7b5a37697c590b0b0.png