题意

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

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

难度

中等

示例

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

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

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

分析 1

这道题对于新手来说，可能第一时间会比较难消化，但耐着性子思考一下，思路就很清晰了。

比如说 2 对应的是 abc，3 对应的是 def，那么 23 对应的就是 ad、ae、af、bd、be、bf、cd、ce、cf。

也就是一个排列组合。

那我们的思路如下：

①、建立一个数字到字母的映射，比如 2 对应的是 abc，3 对应的是 def，我们用数组来就可以。

// 数字到字母的映射
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

0 和 1 属于占位符，没有对应的字母，因为输入的字符串只包含 2-9 的数字。

②、建立一个队列，我们用LinkedList来实现，初始时队列中只有一个空字符串。

LinkedList<String> combinations = new LinkedList<>();
combinations.add(""); // 初始添加一个空字符串到队列中

空字符串是为了方便后续的处理，否则下面这两个方法就没办法直接使用，要判空，很麻烦。

combinations.peek();
String t = combinations.remove();

③、第一层 for 循环，遍历输入的字符串，比如说 23，遍历 2 和 3，排列组合嘛。

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

④、while 循环负责将队列中的字符串取出，并且与上一步中组合过的字母进行组合，比如说输入是 234 的时候，2 与 “” 空字符串组合，结果为 a、b、c，3 与 2 对应的 a、b、c 组合，4 与 23 组合后的 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf" 组合。依次类推。

while (combinations.peek().length() == i) {
	String t = combinations.remove();
	// ...
}

peek() 方法用于获取队列的头部元素，但不会移除这个元素，remove() 方法用于获取队列的头部元素，并且移除这个元素，防止重复组合，用过了就删除。

⑤、第二层 for 循环，遍历当前数字对应的所有字母，比如说 2 对应的是 abc，3 对应的是 def。

for (char s : mapping[digit].toCharArray()) {
	// ...
}

来看完整的题解代码：

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> combinations = new LinkedList<>();
        // 如果输入为空，直接返回空列表
        if (digits == null || digits.length() == 0) {
            return combinations;
        }

        // 数字到字母的映射
        String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        combinations.add(""); // 初始添加一个空字符串到队列中

        // 遍历每个数字
        for (int i = 0; i < digits.length(); i++) {
            int digit = Character.getNumericValue(digits.charAt(i)); // 将当前字符转换为数字
            // 当队列中的字符串长度与当前处理的数字索引相同时，处理队列中的字符串
            while (combinations.peek().length() == i) {
                String t = combinations.remove(); // 从队列中取出一个字符串
                // 遍历当前数字对应的所有字母
                for (char s : mapping[digit].toCharArray()) {
                    combinations.add(t + s); // 将取出的字符串与当前字母相结合，然后加入队列中
                }
            }
        }
        return combinations; // 返回包含所有组合的列表
    }
}

当输入 digits = "23" 时，我们来模拟一下整个题解过程：

初始化

• mapping: {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
• combinations: [""] (初始时只包含一个空字符串)

迭代过程

①、处理数字 '2'（对应 "abc"）

• 从 combinations 中取出 "" (队列现在为空)
• 将 "" 与 "abc" 中的每个字符结合
• 新的组合: ["a", "b", "c"] 加入到队列

③、处理数字 '3'（对应 "def"）

• 从 combinat