1 题目理解
给定一个字符串string,字符范围是[2,9]之间的数字。数字表示电话上的一个按钮。返回字符串的可能所有组合方式。每个数字对应的字母如下图所示。
Example 1:
Input: digits = “23”
Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Example 2:
Input: digits = “”
Output: []
Example 3:
Input: digits = “2”
Output: [“a”,“b”,“c”]
2 回溯
用回溯的方法可以解决。每次处理一个数字,每个数字对应3-4种转换。
这里我自己的一个小技巧是:dfs函数中的变量都是与状态相关的。其他变量都作为成员变量。这样可以更关注dfs过程中的状态。
class Solution {
private Map<Character,String> map = new HashMap<Character,String>(){{
put('2',"abc");
put('3',"def");
put('4',"ghi");
put('5',"jkl");
put('6',"mno");
put('7',"pqrs");
put('8',"tuv");
put('9',"wxyz");
}};
private String digits;
private List<String> answer;
public List<String> letterCombinations(String digits) {
answer = new ArrayList<String>();
if(digits.length()==0) return answer;
StringBuilder str = new StringBuilder();
this.digits = digits;
dfs(0,str);
return answer;
}
private void dfs(int index,StringBuilder str){
if(index == digits.length()){
answer.add(str.toString());
}else{
String value = map.get(digits.charAt(index));
for(int i=0;i<value.length();i++){
str.append(value.charAt(i));
dfs(index+1,str);
str.setLength(str.length()-1);
}
}
}
}