1.题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

2.解题思路与代码

2.1 解题思路

这道题可以使用递归来完成，定义一个当前所指向数字的索引 index，然后根据这个索引 index 获取数字所对应的字母，使用一个 StringBuilder 存放这些字母，然后通过递归函数以继续处理往 index+1 操作，最后当 index 超过给定 digits 长度时表示当前这一组字母组合完毕，将 StringBuilder 内容放入结果数组中，然后返回。返回之后需要清除 StringBuilder 中当前加入的字母，即删除 StringBuilder 最后一个字母。

以 “23” 为例，首先我们从 2 开始，2 包含了字母 abc，因此在 2 这一级有 a、b、c 三个字母。首先我们从字母 a 开始，将字母 a 放入到 StringBuilder 中，然后继续往下处理到数字 3，数字 3 有 d、e、f 三个字母，那么首先将 d 追加到 StringBuilder 中，继续往 index+1 处理，此时 index 超过字符串长度，将 StringBuilder 中的 ad 放入结果列表中。

然后从 StringBuilder 中移除最后一位字母 d，返回到上一级继续向下处理，此时将字母 e 追加到 StringBuilder 中，此时 index+1 超过字符串长度，因此将字符串 ae 放入结果数组当中。之后继续重复上面的这一系列操作，便能够得到所有字母组合的结果列表。

2.2 代码

class Solution {
          
   
    // 使用 Map 存放数字和数字对应字母数组的关系
    private Map<Integer, char[]> map;
    List<String> list = new ArrayList<>();

    public Solution() {
          
   
        map = new HashMap<>();
        char[] two = {
          
   a, b, c};
        char[] three = {
          
   d, e, f};
        char[] four = {
          
   g, h, i};
        char[] five = {
          
   j, k, l};
        char[] six = {
          
   m, n, o};
        char[] seven = {
          
   p, q, r, s};
        char[] eight = {
          
   t, u, v};
        char[] nine = {
          
   w, x, y, z};
        map.put(2, two);
        map.put(3, three);
        map.put(4, four);
        map.put(5, five);
        map.put(6, six);
        map.put(7, seven);
        map.put(8, eight);
        map.put(9, nine);
    }

    public List<String> letterCombinations(String digits) {
          
   
        if ("".equals(digits)){
          
   
            return list;
        }
        process(0,digits,new StringBuilder());
        return list;
    }

    public void process(int index, String digits, StringBuilder builder) {
          
   
        if (index == digits.length()) {
          
   
            list.add(builder.toString());
            return;
        }
        int num = Integer.parseInt(String.valueOf(digits.charAt(index)));
        char[] chars = map.get(num);
        for (int i = 0; i < chars.length; i++) {
          
   
            builder.append(chars[i]);
            process(index + 1, digits, builder);
            builder.delete(builder.length() - 1, builder.length());
        }
    }
}

2.3 测试结果

通过测试

3.总结

使用 Map 存放数字和字母列表的关系 使用递归组装字符串，并且在退出方法时需要删除 StringBuilder 中最后一个字母