题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解答：
递归实现：
public static List<String> letterCombinations(String digits) {
//声明电话号码和字母所对应的集合
List<String> two=new ArrayList(Arrays.asList("a","b","c"));
List<String> three=new ArrayList(Arrays.asList("d","e","f"));
List<String> four=new ArrayList(Arrays.asList("g","h","i"));
List<String> five=new ArrayList(Arrays.asList("j","k","l"));
List<String> six=new ArrayList(Arrays.asList("m","n","o"));
List<String> seven=new ArrayList(Arrays.asList("p","q","r","s"));
List<String> eight=new ArrayList(Arrays.asList("t","u","v"));
List<String> nine=new ArrayList(Arrays.asList("w","x","y","z"));
//嵌套存入集合
List<List<String>> map=new ArrayList(Arrays.asList(two,three,four,five,six,seven,eight,nine));
//声明结果集合
List<String> rStrings=new ArrayList<>();
//边界条件
if (digits.length()==0) {
return rStrings;
}
//求最后一位电话号码对应的字母集合
int first=digits.charAt(0)-'0'-2;
List<String> current=map.get(first);
if (digits.length()==1) {
for (int i = 0; i < current.size(); i++) {
rStrings.add(current.get(i));
}
//返回排列结果，1/多个字符时，将抽取最后一个字符对应的字母集合：这个结果将作为后缀继续排列。
return rStrings;
}
//因为循环次数不确定，所以需要使用递归，不断地截取到只剩一个字符
List<String> leftList=letterCombinations(digits.substring(1));
for (String aList:current) {
for(String str:leftList){
//做一个排列操作
rStrings.add(aList+str);
}
}
for (int i = 0; i < rStrings.size(); i++) {
System.out.print(rStrings.get(i)+";");
}
//返回排列结果，多个字符时，这个结果是中间排列结果，将作为后缀继续排列。
return rStrings;
}
回溯法实现：
public static List<String> letterCombinations(String digits) {
List<String> list = new ArrayList<String>();
if (digits.length() == 0) {
return list;
}
backtracking("", digits, 0, list);// 回溯
return list;
}
/*
* 比如输入1,2。对应的是abc,def。回先从a开始，然后flag+1，依次向下遍历def，
* 然后依次向上返回返回ad,ae,af，并且添加到结果集中，然后再向上返回到i=0的循环
* 然后i+1，从b开始，再依次向下遍历def，如同a一样，依次返回所有结果，当所有的遍历完之和，返回到letterCombinations中结束。
*/
public static void backtracking(String s, String digits, int flag, List<String> list) {
String[] strings = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
if (flag >= digits.length()) {// 如果已经遍历完所有输入的数字，说明已经到达底部，需要向上溯源。
list.add(s);// 到达底部说明已经是完整的一个结果，则将此次结果添加到结果集中
return;// 返回，向上回溯
}
String chars = strings[digits.charAt(flag) - '0'];
// 遍历一个数字对应的所有字母
for (int i = 0; i < chars.length(); i++) {
// 将当前字符加到s上并将flag+1循环下一个数字的字母
backtracking(s + chars.charAt(i), digits, flag + 1, list);
}
}
