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'] 的一个数字。

//递归
//思路：按照顺序添加字母，递归过程中一个分支走完直接添加到全局变量ans中

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans=new ArrayList<>();
        if (digits.length() == 0) {
            return ans;
        }
        Map<Character, String> phoneMap = 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");
        }};

        backtrace(ans, phoneMap,digits,0,"");
        return ans;
    }


    public static void backtrace(List<String> ans,Map<Character, String> phonemap,String digits,int index,String combine){
        //一个分支添加完毕，添加到ans中
        if(index==digits.length())
            ans.add(combine);
        else {
            for(int i=0;i<phonemap.get(digits.charAt(index)).length();i++){
                combine=combine+phonemap.get(digits.charAt(index)).charAt(i);
                backtrace(ans,phonemap, digits,index+1, combine);
                //向上层返回，删除掉刚添加的字符
                combine=combine.substring(0, combine.length()-1);
            }
        }

    }
}