给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = ""
输出:[]
示例 3:
输入:digits = "2"
输出:["a","b","c"]
思路
题目中说的是组合,可以采用回溯法的方法来解答,但是有一些变种
-
需要维护一个map来保存0 - 9的字符床
-
维护一个start指针,代表当前搜索的字符
-
select_list = map.get(str.charAt(start));
回溯的时候 因为手机的一个按键只能按一次,但是会出现3种情况,接着就是下一个按键(可重复)
-
-
回溯的结束条件为start >= str.length
关键代码
public List<String> letterCombinations(String digits) {
List<String> resultList = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return resultList;
}
Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
// 选择列表
StringBuilder sb = new StringBuilder();
int start = 0;
trackBackFunction(digits, resultList, start, sb, map);
return resultList;
}
private void trackBackFunction(String digits, List<String> resultList, int start, StringBuilder sb, Map<Character, String> map) {
if (start == digits.length()) {
resultList.add(sb.toString());
return;
}
String selectList = map.get(digits.charAt(start));
for (int i = 0; i < selectList.length(); i++) {
sb.append(selectList.charAt(i));
// 需要注意的是这里需要start + 1或者 ++start, 而不能用start++
trackBackFunction(digits, resultList, start + 1, sb, map);
sb.deleteCharAt(sb.length() - 1);
}
}