17.电话号码的字母集合

题目描述：

给定一个仅包含数字 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);
        }
    }