17. 电话号码的字母组合

红太狼 2024-03-31 13:08 58阅读 0赞

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

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

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

##### 示例 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’\] 的一个数字。

#### 思路：（回溯） ####

Backtracking（回溯）属于 DFS。

*  普通 DFS 主要用在 **可达性问题** ，这种问题只需要执行到特定的位置然后返回即可。
 *  而 Backtracking 主要用于求解 **排列组合** 问题，例如有 \{ ‘a’,‘b’,‘c’ \} 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

*  在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
 *  但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素

#### 代码：(Java) ####

import java.util.List;
    import java.util.ArrayList;
    
    public class letter_combination {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		String digits = "23";
    		System.out.println(letterCombinations(digits));
    
    	}
    	private static final String[] keys = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    	
    	public static List<String> letterCombinations(String digits) {
        
    		List<String> combinations = new ArrayList<>();
    		if(digits == null || digits.length() == 0) {
        
    			return combinations;
    		}
    		doCombination(new StringBuilder(), combinations,digits);
    		return combinations;
        }
    
    	private static void doCombination(StringBuilder prefix, List<String> combinations, String digits) {
        
    		// TODO 自动生成的方法存根
    		if(prefix.length() == digits.length()) {
        
    			combinations.add(prefix.toString());
    			return;
    		}
    		int curDigits = digits.charAt(prefix.length()) - '0';
    		String letters = keys[curDigits];
    		for(char c : letters.toCharArray()) {
        
    			prefix.append(c);
    			doCombination(prefix, combinations,digits);
    			prefix.deleteCharAt(prefix.length() - 1);
    		}
    	}
    }

##### 输出： #####

![在这里插入图片描述][6db136f0779a4b94aa15480662a55589.png]

##### 复杂度分析： #####

时间复杂度： O ( 3 m × 4 n ) O(3^m×4^n) O(3m×4n)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n个对应 4 个字母的数字时，不同的字母组合一共有  3 m × 4 n 3^m×4^n 3m×4n种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n是输入数字的总个数。

##### 注：仅供学习参考！ #####

题目来源：[力扣][Link 1]

[50dd74fb7b6e4c9d9d3cbf258c7aee5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8e498508e73247f6bc63ff37a53d68fb.png
[6db136f0779a4b94aa15480662a55589.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bdc21dfb761541aa83ba1bde3ab7860d.png
[Link 1]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/