LeetCode_06_LetterCombinationsOfAPhoneNumber

1. question：电话号码的字母组合（中等）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

2. answer

思路：

这道题没什么可说的，就是一个排列组合问题。

可以先用递归的思路做一下：即一个电话号码 “2345”的字母组合是由 “234”的字母组合 和 “5” 重新组合形成的，而 “234” 的字母组合是由 “23” 的字母组合 和 “4” 重新组合形成的。

首先将映射关系准备好，用HashMap存储。然后用 List 存储结果。注意更新结果的时候，一部分是在原有的组合上更新，一部分是新增组合。

比如最开始ArrayList是空的，字符串是“234”，
          第一次遍历2，将2对应的 "a", "b", "c"加入到ArrayList中
          第二次遍历3，此时ArrayList中已经存在组合了，这是将3对应的 "d", "e", "f" 和已经存在的组合重新组合。
          第三次遍历4，重复上述步骤，直到遍历结束。

代码如下所示：

public class Solution_0006 {

    public static Map<Character, String[]> map = new HashMap<>();

    static {
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
    }

    public static List<String> getLetterList(List<String> result, String digits){

        // 递归结束
        if(digits.length() == 0){
            return result;
        }

        // 判断ArrayList中是否存在组合，没有的话，则直接将字符添加即可
        if(result.size() == 0){

            for (int i = 0; i < map.get(digits.charAt(0)).length; i++) {
                result.add(i, map.get(digits.charAt(0))[i]);
            }
        } else {

            // 存在组合，则需要重新组合
            int size = result.size();

            // 遍历字符串中第一个字符对应的字母数组
            for (int i = 0; i < map.get(digits.charAt(0)).length; i++) {
                for (int j = 0; j < size; j++) {
                    // 修改原有的组合
                    if(j + i * size < size){
                        result.set(j + i * size, result.get(j) + map.get(digits.charAt(0))[i]);
                    } else{
                        // 添加新的组合
                        // 注意，因为已经修改了原有的组合，所以后续组合的时候，需要取到原有的组合，
                        // 而新的组合其实就是添加了一个字符，所以获取原有的组合就是去掉一个字符，即result.get(j).length() - 1)
                        // 然后再将 遍历字符对应的数组 和 原有组合 进行组合
                        result.add(result.get(j).substring(0, result.get(j).length() - 1) + map.get(digits.charAt(0))[i]);
                    }
                }
            }
        }

        // 递归，将遍历后的字符去掉，遍历剩余的字符串。
        result = getLetterList(result, digits.substring(1));

        return result;
    }

    public static List<String> letterCombinations(String digits) {

        List<String> result = new ArrayList<>();

        return getLetterList(result, digits);
    }

    public static void main(String[] args) {

        String digits = "23";
//        String digits = "3";
//        String digits = "";

        List<String> result = letterCombinations(digits);

        for (String s : result) {
            System.out.println(s);
        }
    }
}

经过上述递归，其实可以转为非递归，即三层循环。代码如下所示：

public class Solution_0006_02 {

    public static Map<Character, String[]> map = new HashMap<>();

    static {
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
    }

    public static List<String> letterCombinations(String digits) {

        List<String> result = new ArrayList<>();

        char[] chars = digits.toCharArray();

        int size;

        for (int i = 0; i < digits.length(); i++) {

            // 遍历该元素前先获取result中的组合个数，用于后续重新组合
            size = result.size();

            // 遍历该数字对应的所有字符，进行组合
            for (int j = 0; j < map.get(chars[i]).length; j++) {

                if(size == 0){
                    result.add(map.get(chars[i])[j]);
                } else {
                    for (int k = 0; k < size; k++) {
                        // 修改原有的组合
                        if(k + j * size < size){
                            result.set(k + j * size, result.get(k) + map.get(chars[i])[j]);
                        } else{
                            // 添加新的组合
                            // 注意，因为已经修改了原有的组合，所以后续组合的时候，需要取到原有的组合，
                            // 而新的组合其实就是添加了一个字符，所以获取原有的组合就是去掉一个字符，即result.get(j).length() - 1)
                            // 然后再将 遍历字符对应的数组 和 原有组合 进行组合
                            result.add(result.get(k).substring(0, result.get(k).length() - 1) + map.get(chars[i])[j]);
                        }
                    }
                }
            }
        }


        return result;
    }

    public static void main(String[] args) {
//        String digits = "23";
//        String digits = "3";
        String digits = "";

        List<String> result = letterCombinations(digits);

        for (String s : result) {
            System.out.println(s);
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)。