黑龙江生产建设兵团知青网站宝安网站(建设深圳信科)

一、题目描述

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"

输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""

输出：[]

示例 3：

输入：digits = "2"

输出：["a","b","c"]

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

三、解题思路

这里是参考官方给出的解题思路，本人想的也是用回溯法，但是奈何不懂回溯怎么写org，仅以此博文记录，权当加深理解。

首先用一个哈希表将每个数字对应的字母串，然后进行回溯遍历，具体如下：

如果当前字母组合的长度和原数字串的长度相等，则表示已经得到了一个满足的字母组合，将该字母串加入到结果列表中；（递归出口）

如果不相等，表示还没有遍历完数字串，则取出当前下标的数字，根据数字从哈希表中取出其对应的字母串，获取这个字母串的长度（字母个数），然后对这个字母串的每个字母进行处理：

首先出去该字母，然后将该字母加入到作为参数传递的字母串后面，再递归对下一个数字进行同样的处理，最后是回溯（将当前字母从字母串中删除，避免重复遍历）。

ps: 回溯是通过递归实现的，所以最前面要定义递归出口，最重要的是在要在递归后面删掉当前字母，这就是回溯。

四、AC代码

class Solution {public List<String> letterCombinations(String digits) {int len = digits.length();List<String> ans = new ArrayList<>();if(len == 0) return ans;//双花括号初始化 匿名内部类 初始化块Map<Character, String> numMap = new HashMap<>(){{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};StringBuffer sb = new StringBuffer();trackback(digits, numMap, ans, 0, sb);return ans;}//回溯（用递归的方式实现）public void trackback(String digits, Map<Character, String> phoneMap, List<String> ans, int index, StringBuffer sb){if(index == digits.length()){ans.add(sb.toString());} else {char num = digits.charAt(index);String letters = phoneMap.get(num); //当前数字对应的字母串int letCount = letters.length(); //当前数字对应的字母个数for(int i=0; i<letCount; ++i){char c = letters.charAt(i);sb.append(c);  //加入当前字母trackback(digits, phoneMap, ans, index+1, sb);  //递归处理下一个数字sb.deleteCharAt(index); //回溯}}}
}