LeetCode Hot100（17. 电话号码的字母组合）

17. 电话号码的字母组合

给定一个仅包含数字 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'] 的一个数字。

解答：递归+回溯统计所有出现的结果

class Solution {
    List<String> res=new ArrayList<>();
    StringBuilder sb=new StringBuilder();
    public List<String> letterCombinations(String digits) {
                 //0，  1     2    3     4     5      6     7     8      9
    String[] nums={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    if(digits==null||digits.length()==0)return res;
    backing(digits,nums,0);
    return res;
    }
    void backing(String digits,String[] nums,int start){
        //满足条件，加到答案里
        if(start==digits.length()){
            res.add(sb.toString());
            return;
        }
        //找出现在的数字对应的字母
        String curnum=nums[digits.charAt(start)-'0'];
        //递归回溯
        for(int i=0;i<curnum.length();i++){
           sb.append(curnum.charAt(i));
           backing(digits,nums,start+1);
           sb.deleteCharAt(sb.length()-1); 
        }
    }
}