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

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

示例:

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

class Solution {
    /***

    ***/
Map<String, String> phone = new HashMap<String, 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");
  }};
List<String> list = new LinkedList<>();
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        if(len == 0) return list;
        backtrack("",digits);
        return list;
    }
    //处理字符串，str代表已经生成的字符，next_str代表剩下的数字
    public void backtrack(String str,String next_str){
        if(next_str.length() == 0){
            list.add(str);
        }else{
            //获取第一位换成相应字符遍历n次加入到str上，然后处理next_str(1,len)
            String s = next_str.substring(0,1);
            String s1 = phone.get(s);
            for(int i = 0;i < s1.length();i++){
                String s2 = s1.substring(i,i+1);
                backtrack(str+s2,next_str.substring(1));
            }
        }
    }
}