题目

力扣题目链接

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

思路

从示例上来说，输入”23”，最直接的想法就是两层for循环遍历了吧，正好把组合的情况都输出了。

如果输入”233” 呢，那么就三层 for 循环，如果 “2333” 呢，就四层 for 循环…….

大家应该感觉出和 77.组合 遇到的一样的问题，就是这 for 循环的层数如何写出来，此时又是回溯法登场的时候了。

那么，本题与 77.组合、216.组合总和III 这两题有什么区别呢？

本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而 77.组合、216.组合总和III 都是求同一个集合中的组合。

理解本题后，要解决如下三个问题：

  1. 两个字母就两个 for 循环，三个字符我就三个 for 循环，以此类推，然后发现代码根本写不出来
  2. 数字和字母如何映射
  3. 输入1 * #按键等等异常情况

问题 1 我们很清楚了，可以用回溯法来解决 n 个 for 循环的问题。

例如：输入：”23”，抽象为树形结构，如图所示：
image.png
图中可以看出遍历的深度，就是输入”23”的长度，而叶子节点就是我们要收集的结果，输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

那么问题 2 和 问题 3 呢？

数字和字母如何映射

可以使用 map 或者 二维数组，例如：String[] letterMap，来做映射，我这里定义一个二维数组，代码如下：

String[] letterMap = {
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
    };

异常情况

代码中最好考虑输入1 #按键等这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。
*但是要知道会有这些异常，如果是现场面试中，一定要考虑到！

关键地方都讲完了，剩下按照回溯三部曲就可以写出代码了。

答案

Java

class Solution {
    String digits = null;
    List<String> result = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    String[] letterMap = new String[]{
            "", // 0
            "", // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz", // 9
    };

    // 入口
    public List<String> letterCombinations(String digits) {
        this.digits = digits;

        backtracking(0);

        return result;
    }

    void backtracking(int index) {
        if (path.length() == digits.length()) {
            result.add(path.toString());
            return;
        }

        // 将 digits[index] 指向的数字转为 int
        int digit = digits.charAt(index) - '0';
        // 取数字对应的字符集
        String str = letterMap[digit];
        // 遍历每一个字符
        for (int i = 0; i < str.length(); i++) {
            // 处理
            path.append(str.charAt(i));
            // 递归，注意 index+1，下一层要处理下一个数字 digits[index+1] 了
            backtracking(index);
            // 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
}

REF

https://programmercarl.com/0017.电话号码的字母组合.html
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/