解法要点题目链接：力扣https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
这题是一道典型的采用深度优先遍历的算法题，提到深度优先遍历，那基本就要跟递归挂钩了。不过一般面试也不会出这题吧，现在用九宫格键盘的也不多，候选人也不大记得键盘布局，出这个题，面试官还得自己画个键盘，也太麻烦了。
言归正传，回到我上上篇博客（括号生成）关于递归的理解，咱们来设计一下这个递归函数的签名，它应该是
dfs(int idx, String digits, String str)
为什么呢，要注意下面几点
1.首先，考虑递归出口，idx 是指我们当前处理的是按下的第几个字母（下标从0开始），当 idx == digits.length() 时，就说明已经遍历到最后一个按键了，深度遍历结束，把当前结果 str 放到结果集合中就行了；
2.digits 其实没变，就是输入的字母组合，你可以不放到递归签名中，搞个全局变量也一样；
3.递归中每一步该做什么呢？有了 idx 和 digits，我们就能找到当前遍历到的数字，也就是 numChar = digits.charAt(idx)。这里有一个小技巧，我们把电话上数字和字母的映射关系用一个数组存储，让这个数组的下标和电话键盘上的数字一一映射，也就是 letterMap，比如，下标 0 和 1 对应的空字符串，下标 2对应的数组元素是“abc”。所以，根据数字，就能找到其对应的字母组成的字符串，就是 letterMap[numChar - '0']，因为这里的数字是 char，所以要减去字符0，转换为 int；
4.有了数字对应的字母组成的字符串，将其转换为字符数组，然后遍历，每次将其中一个字母追加到最终结果 str 尾部，同时 idx 加 1，意思是下一次递归，就会 append 下一个数字对应的字母，这样就 OK 啦。所以，操作下一步的代码是 dfs(idx+1, digits, str+c)，c 是当前数字按键上的一个字母。
class Solution {
private String letterMap[] = {
"", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
List ansList = new ArrayList<>();
public List letterCombinations(String digits) {
// 先判空
if(digits == null || digits.length() == 0){
return ansList;
}
// 从第 0 个按键输入开始遍历，初始字符串是空
dfs(0, digits, "");
return ansList;
}
// digits 其实可以跟 letterMap 一样，做成全局变量，没必要每次都在递归中传递
// idx 表示当前遍历到第几个输入的数字
// str 表示当前深度遍历正在组合中的一个结果
public void dfs(int idx, String digits, String str){
if(idx == digits.length()){
// 遍历完成，结束递归
ansList.add(str);
return;
}
// 获取当前数字对应的字母组成的字符串
String letters = letterMap[digits.charAt(idx) - '0'];
for(char c : letters.toCharArray()){
// 每次将字符串中的一个字母加入结果中，同时开启一个新的递归分支
dfs(idx+1, digits, str+c);
}
}
}
代码就是这样了，很简单，但是里面的小技巧要记牢，比如用数组代替 map（当然，你可以直接用 map，不是往里塞 KV 费事儿吗），用减去字符0完成 char 到 int 的转换，还有递归的套路，这些在别的题目中也很可能遇到，就这些了，明天见~
现在，关于电话号码的字母组合这道题，你已经知道得和我一样多了~
本专栏定期更新力扣算法讲解，希望以最容易记忆的方式帮你搞定面试算法题。
