每日一道算法题：电话号码的字母组合算法实现

算法概述

本算法用于求解给定电话号码的所有可能的字母组合。电话号码由数字构成，每个数字分别对应一些字母，我们需要找出所有可能的字母组合。

电话号码所表示的字母

由于电话号码由数字构成，每个数字分别对应一些字母，因此我们需要先构建数字与字母的映射关系。

以下是数字与字母的对应关系：

算法实现过程

1. 输入电话号码
2. 构建数字与字母的映射关系
3. 深度优先搜索找出所有的组合

其中，第3步需要递归实现。

具体实现细节将在接下来的代码实现中详细阐述。

代码实现

输入电话号码的函数

private static String getInput() {
    Scanner sc = new Scanner(System.in);
    String input;
    do {
        System.out.print("请输入电话号码(仅包含2-9范围内的数字)：");
        input = sc.nextLine();
    } while(!isInputValid(input));
    return input;
}

此函数用于读取用户输入的电话号码。

构建数字与字母的映射关系的函数

private static void buildMap(Map<Character, List<Character>> map) {
    map.put('2', Arrays.asList('a', 'b', 'c'));
    map.put('3', Arrays.asList('d', 'e', 'f'));
    map.put('4', Arrays.asList('g', 'h', 'i'));
    map.put('5', Arrays.asList('j', 'k', 'l'));
    map.put('6', Arrays.asList('m', 'n', 'o'));
    map.put('7', Arrays.asList('p', 'q', 'r', 's'));
    map.put('8', Arrays.asList('t', 'u', 'v'));
    map.put('9', Arrays.asList('w', 'x', 'y', 'z'));
}

此函数用于构建数字与字母的映射关系。

深度优先搜索的函数

private static void dfs(Map<Character, List<Character>> map, String digits, String combination, List<String> combinations) {
    if(digits.length() == 0) { // 递归边界
        combinations.add(combination); // 加入结果集
    }else {
        Character digit = digits.charAt(0); // 取出第一个数字
        List<Character> letters = map.get(digit); // 取出该数字对应的所有字母
        for(Character letter:letters) { // 依次尝试每个字母
            dfs(map, digits.substring(1), combination + letter, combinations); // 递归下一层
        }
    }
}

此函数用于深度优先搜索，调用函数时，需传入以下参数：

• Map<Character, List<Character>> map：数字与字母的映射关系。
• String digits：待处理的电话号码。
• String combination：已生成的字母组合。
• List<String> combinations：存放所有可能的字母组合。

主函数

public static void main(String[] args) {
    String digits = getInput(); // 输入电话号码
    Map<Character, List<Character>> map = new HashMap<>();
    buildMap(map); // 构建数字与字母的映射关系
    List<String> combinations = new ArrayList<>();
    dfs(map, digits, "", combinations); // 深度优先搜索
    System.out.println("电话号码" + digits + "对应的所有可能的字母组合为：" + combinations);
}

此函数为程序入口，调用了前面提到的3个函数，找出所有可能的字母组合，并输出。

算法测试

测试1：

输入：23

输出：电话号码23对应的所有可能的字母组合为：[ad, ae, af, bd, be, bf, cd, ce, cf]

测试2：

输入：79

输出：电话号码79对应的所有可能的字母组合为：[pw, px, py, pz, qw, qx, qy, qz, rw, rx, ry, rz, sw, sx, sy, sz]

算法优化

剪枝优化

由于存在多个数字对应同一组字母，因此可以在搜索的时候增加一个剪枝操作，以减少无用的搜索。

private static void dfs(Map<Character, List<Character>> map, String digits, String combination, List<String> combinations) {
    if(digits.length() == 0) { // 递归边界
        combinations.add(combination); // 加入结果集
    }else {
        Character digit = digits.charAt(0); // 取出第一个数字
        List<Character> letters = map.get(digit); // 取出该数字对应的所有字母
        for(Character letter:letters) { // 依次尝试每个字母
            dfs(map, digits.substring(1), combination + letter, combinations); // 递归下一层
        }
    }
}

可以在循环体中加入以下判断：

if(combinations.size() >= 5000) { // 如果结果集数量超过5000，则退出搜索
    break;
}

当结果集数量超过5000时，直接退出搜索，避免无用的搜索。

数组优化

由于数字对应的字母都是固定的，可以考虑将字母表构造成一个String类型的数组。

private static void dfs(String[] map, String digits, String combination, List<String> combinations) {
    if(digits.length() == 0) { // 递归边界
        combinations.add(combination); // 加入结果集
    }else {
        char digit = digits.charAt(0); // 取出第一个数字
        String letters = map[digit - '2']; // 取出该数字对应的所有字母
        for(int i = 0; i < letters.length(); i++) { // 依次尝试每个字母
            dfs(map, digits.substring(1), combination + letters.charAt(i), combinations); // 递归下一层
        }
    }
}

由于字符的ASCII码是连续的，因此可以通过计算字符的差值来获取数字。

同样，建立数字和字母表的映射关系可以改为：

private static void buildMap(String[] map) {
    map[0] = "abc";
    map[1] = "def";
    map[2] = "ghi";
    map[3] = "jkl";
    map[4] = "mno";
    map[5] = "pqrs";
    map[6] = "tuv";
    map[7] = "wxyz";
}

并在主函数中进行调用：

public static void main(String[] args) {
    String digits = getInput();
    String[] map = new String[8];
    buildMap(map);
    List<String> combinations = new ArrayList<>();
    dfs(map, digits, "", combinations);
    System.out.println("电话号码" + digits + "对应的所有可能的字母组合为：" + combinations);
}

对于小数据量的测试用例来说，这样的优化效果可能并不明显，但在数据量大的情况下，优化后的代码可以更大程度上地提升程序的性能。

扩展问题

输入多个电话号码，求它们所有字母组合的并集

思路：将每个号码求出对应的所有字母组合，并存储到一个集合中。最后将所有集合取并集即可。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.print("请输入电话号码数量：");
    int n = sc.nextInt(); sc.nextLine();
    String[] digits = new String[n];
    for(int i = 0; i < n; i++) {
        digits[i] = getInput();
    }
    String[] map = new String[8];
    buildMap(map);
    Set<String> set = new HashSet<>();
    for(int i = 0; i < n; i++) {
        List<String> combinations = new ArrayList<>();
        dfs(map, digits[i], "", combinations);
        set.addAll(combinations);
    }
    System.out.println("所有电话号码对应的所有可能的字母组合为：" + set);
}

输入一个字符串和一个电话号码，求字符串中是否包含电话号码所表示的所有字母组合

思路：先将电话号码对应的所有字母组合求出来，再依次判断字符串中是否包含该组合即可。

public static void main(String[] args) {
    String digits = getInput();
    String[] map = new String[8];
    buildMap(map);
    List<String> combinations = new ArrayList<>();
    dfs(map, digits, "", combinations);
    System.out.println("电话号码" + digits + "对应的所有可能的字母组合为：" + combinations);

    Scanner sc = new Scanner(System.in);
    System.out.print("请输入字符串：");
    String str = sc.nextLine();
    boolean flag = true;
    for(String combination:combinations) {
        if(!str.contains(combination)) {
            flag = false;
            break;
        }
    }
    if(flag) {
        System.out.println("字符串中包含电话号码对应的所有字母组合");
    }else {
        System.out.println("字符串中不包含电话号码对应的所有字母组合");
    }
}

需要注意的是，输入的字符串和电话号码都要进行非空和合法性验证。