本文共 1660 字，大约阅读时间需要 5 分钟。

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

来源：力扣（LeetCode）

解答：

思路：如果采用循环来做这道题，那么返回列表的大小会随着输入数字字符串的长度呈几何级上升，显然不能这样做。所以这道题应该采用回溯的方法，每次输入回溯方法的数字字符创的长度减一，输入的数字字符串的第一个数字对应多少个字母，那么在这重的回溯方法中就打开多少个回溯程序，同时，将第一个数字对应的字母挂在对应输入回溯程序的输入中，这样每一重回溯方法，这个字符串都会加长一位。最后当回溯程序输入的数字字符串的长度为0是，就在列表里加入和这个数字字符串输入回溯程序的字符串。

代码（Java）：

public class Solution{
   	public static void main(String[] args) {
   		String digits = "234";		System.out.println(letterCombinations(digits));			}		static Map
   
     phone = new HashMap
    
     (){
   {
     //静态块的声明，准备工作		put("2","abc");  //把数字和对应的字母分别作为key和value放在Map里面		put("3","def");		put("4","ghi");		put("5","jkl");		put("6","mno");		put("7","pqrs");		put("8","tuv");		put("9","wxyz");	}};	static List
     
       output = new ArrayList
      
       (); //出书画一个List用来存放输出的字符串集			public static List
       
         letterCombinations(String digits){
   		if(digits.length()!=0) {
   			backrack("",digits);  //回溯的方法，开始的输入是combination为空，逐渐往里面添加字符，输入这个数字字符串		}		return output;	}	public static void backrack(String combination, String next_digit) {
     //回溯方法		if(next_digit.length()==0) {
    //每次在执行具体的内容前，先检测输入的next_digit是不是为空，每次回溯调用这个方 法，			       //next_digit的长度都会减少1，当next_digit的长度为0时，把这个字符串添加到output里面，这个是目标字符串之一			output.add(combination);		}		else {
   				String digit = next_digit.substring(0, 1); //取到回溯法舒服数字字符串的第一个数字			String letters = phone.get(digit);  //拿到这个数字对应的字母			for(int i = 0;i
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_39224015/article/details/105647168 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！