题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2‘, ‘9‘] 的一个数字。
方法
回溯
- 时间复杂度：O()
- 空间复杂度：O()
class Solution {
private List<String> result = new ArrayList<>();
private StringBuffer tmp = new StringBuffer();
private Map<Character,String> map = 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");
}};
public List<String> letterCombinations(String digits) {
if(digits==null||digits.length()<1){
return result;
}
dfs(digits,0);
return result;
}
private void dfs(String digits,int depth){
if(depth==digits.length()){
result.add(tmp.toString());
return;
}
String str = map.get(digits.charAt(depth));
for(char c:str.toCharArray()){
tmp.append(c);
dfs(digits,depth+1);
tmp.deleteCharAt(tmp.length()-1);
}
}
}