17. 电话号码的字母组合(一般)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

思路：

排列树，回溯

代码：

class Solution {
    public List<String> letterCombinations(String digits) {
        //最后的结果
        List<String> combinations = new ArrayList<>();
        if(digits.length()==0){
            return combinations;
        }
        Map<Character, String> phone = Map.of(
           '2',"abc",
           '3',"def",
           '4',"ghi",
           '5',"jkl",
           '6',"mno",
           '7',"pqrs",
           '8',"tuv",
           '9',"wxyz"
        );
        backTrack(digits,combinations,phone,0,new StringBuilder());
        return combinations;
    }

    void backTrack(String digits,List<String> combinations,Map<Character, String> phone,int index,StringBuilder combination){
        //排列树
        //index表示排列的下标
        if(index==digits.length()){
            combinations.add(combination.toString());
        }else{
            //找下一个位置
            char digit = digits.charAt(index);
            String value = phone.get(digit);
            int len = value.length();
            for(int i=0;i<len;i++){
                combination.append(value.charAt(i));
                //回溯下一层
                backTrack(digits,combinations,phone,index+1,combination);
                //combination.delete(value.charAt(i));
                combination.deleteCharAt(index);
            }
        }
    }
}