问题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
leetcode-17：电话号码的字母组合 - 图1

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

示例 2：
输入：digits = ""
输出：[]

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

思路

本题需要解决如下三个问题

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

数字和字母如何映射

可以使用map或者定义一个二位数组

  1. private String letterMap[] = {
  2.             " ",    //0
  3.             "",     //1
  4.             "abc",  //2
  5.             "def",  //3
  6.             "ghi",  //4
  7.             "jkl",  //5
  8.             "mno",  //6
  9.             "pqrs", //7
  10.             "tuv",  //8
  11.             "wxyz"  //9
  12.     };
  14. Map<Character, String> phoneMap = new HashMap<Character, String>() {{
  15.             put('2', "abc");
  16.             put('3', "def");
  17.             put('4', "ghi");
  18.             put('5', "jkl");
  19.             put('6', "mno");
  20.             put('7', "pqrs");
  21.             put('8', "tuv");
  22.             put('9', "wxyz");
  23.         }};

回溯法来解决n个for循环的问题

例如：输入："23"，抽象为树形结构，如图所示：
leetcode-17：电话号码的字母组合 - 图2
图中可以看出遍历的深度，就是输入"23"的长度，而叶子节点就是我们要收集的结果，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

回溯三部曲：

  • 确定回溯函数参数

    • 首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局
    • 再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index
    • 这个index可不是之前提及到的startIndex，这个index是记录遍历第几个数字了，就是用来遍历digits（题目中给出数字字符串），同时index也表示树的深度
      List<string> result = new ArrayList<>();
StringBuilder s = new StringBuilder();
void backtracking(string digits, int index)

  • 确定终止条件

    • 例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。那么终止条件就是如果index等于输入的数字个数（digits.length）了（本来index就是用来遍历digits的）。然后收集结果，结束本层递归
      if (index == digits.length()) {
result.add(s.toString());
return;
}

  • 确定单层遍历逻辑

    • 首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）
    • 然后for循环来处理这个字符集，代码如下： ```java Character c = digits.charAt(index); // 将index指向的数字转为char String letters = letterMap[c - ‘0’]; // 取数字对应的字符集 for (int i = 0; i < letters.length(); i++) { s.append(letters.charAt(i)); // 处理 backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了 s.deleteCharAt(s.length() - 1); // 回溯 }

<a name="Z5C5o"></a>
## 输入1 * #按键等等异常情况

```java
class Solution {
    List<String> result = new ArrayList<String>();
    StringBuilder s = new StringBuilder();

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

    public void backtracking(String digits, int index) {
        if (index == digits.length()) {
            result.add(s.toString());
            return;
        }

        Character c = digits.charAt(index);       
        String letters = letterMap[c - '0'];  //注意数组和字符串  
        for (int i = 0; i < letters.length(); i++) {
            s.append(letters.charAt(i));            
            backtracking(digits, index + 1);    
            s.deleteCharAt(s.length() - 1);                       
        }
    }

    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
}
  • 时间复杂度：leetcode-17：电话号码的字母组合 - 图3，其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数，m+n 是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，不同的字母组合一共有 leetcode-17：电话号码的字母组合 - 图4种，需要遍历每一种字母组合
  • 空间复杂度：leetcode-17：电话号码的字母组合 - 图5，除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n