1、题目描述
?
2、算法分析
????????这是一道多集合的回溯算法。
????????回溯算法是基于递归算法的。在递归算法的基础上进行回溯。
????????回溯算法一般题型有：组合，排序，切割，子集，棋盘等
????????其中最最重要的是回溯函数的构造，一般返回值是void，函数命名是backTracking()，里面的函数视情况而定。
? ? ? ? 本题是一个多集合组合的回溯函数。
①回溯函数的确定
? ? ? ? 回溯函数中有3个参数
????????digits代表按键23456789
????????numString?代表的是某个按键对应的字符abc?def ...
????????num代表第几个数?
? ? ? ? 然后使用String存储每个按键的字符
? ? ? ? 遍历这个按键对应的字母，使用这个for循环确定
? ? ? ? 递归函数，记得num+1，进行拼凑
? ? ? ? 最后进行回溯
②递归结束条件的确定
? ? ? ? 当num（第几个数）等于digits字符串长度的时候，架构path添加到结果集。
?下面看代码
3、代码实现
class Solution {
List<String> result = new ArrayList<>();
StringBuilder path = new StringBuilder();
public List<String> letterCombinations(String digits) {
if(digits == null || digits.length() == 0){
return result;
}
String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backTracking(digits,numString,0);
return result;
}
// digits代表按键23，numString 代表的是按键对应的字符abc def，num代表第几个数 2
public void backTracking(String digits,String[] numString,int num){
// num到最后一个数，等于digits字符串的长度的时候
if(num == digits.length()){
result.add(path.toString());
return;
}
// strNum数字对应的字符串
String strNum = numString[digits.charAt(num) - '0'];
for(int i = 0;i < strNum.length();i++){
path.append(strNum.charAt(i));
// 遍历第num+1个字符串，然后分配
backTracking(digits,numString,num + 1);
path.deleteCharAt(path.length() - 1);
}
}
}