力扣17-电话号码的数字组合

题目链接

思路

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”

思路：
电话号码中的一个数字可以对应到多个字母，例如2对应a、b、c。要求23对应的字母组合，就是把2和3对应的字母进行组合。
在每次组合的过程中，一个数字只能取一个字母，不能连续两个字母来自同一个数字；
思考：
问题1：如何收集一个可能的组合？
问题2：在收集到一种组合后，如何继续收集第二种组合？
对于问题1：用暴力法可以解决，每层循环枚举一个数字对应的字母，但是电话号码串很长，循环嵌套深，代码不易好编写
可以采用递归的方式，每层进入递归函数，尝试一个数字对应的点好号码
进入函数，可以想向成进入一棵树的下一层，当递归的深度到达电话号码长度，即到达叶子节点，则返回。
问题3：在递归的每一层做什么？
递归纵向是进入树下一层，即电话号码中的一个数字，在同一层，应该去枚举这个数字对应的字母，这样就可以将当前层的字母，与上一层的字母进行结合，形成答案的一部分，，
问题4：递归什么时候结束？
到达电话号码的长度时，应该往树的上一层返回。

这里的往下递，和往上归，即回溯法，往下遍历是搜索，往上是回溯；回退到上一层，当前数字对应的字母就丢弃了，
比如 2,3; 3是第二层，遍历得到的字母组合是ab, 已经达到电话号码长度，往上一层回溯时b应该就被丢弃。

因此，本题使用回溯法，纵向遍历电话号码中的每个数字，横向遍历每个数字对应的字母，达到电话号码长度时收集一种组合，并往上一层回溯。

代码

class Solution {private List<String> ans;private String[][] dic = {{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};public List<String> letterCombinations(String digits) {ans = new ArrayList<>();if (digits.length()==0) {return ans;}Map<String,String> m = new HashMap<>();for (int i=0, n=dic.length; i<n; i++) {m.put(dic[i][0]+"", dic[i][1]+"");}String path = "";dfs(digits, m, 0, path);return ans;}public void dfs(String digits, Map<String, String> mp, int i, String path) {int n = digits.length();if (i>=n) {ans.add(new String(path));return;}String t = mp.get(digits.charAt(i)+"");for (int j=0, m=t.length(); j<m; j++) {dfs(digits, mp, i+1, path+t.charAt(j));}}
}