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

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

示例 1：

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

示例 2：

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

示例 3：

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

思路

题目中说的是组合，可以采用回溯法的方法来解答，但是有一些变种

• 需要维护一个map来保存0 - 9的字符床

• 维护一个start指针，代表当前搜索的字符

  • select_list = map.get(str.charAt(start));

    回溯的时候 因为手机的一个按键只能按一次，但是会出现3种情况，接着就是下一个按键（可重复）

• 回溯的结束条件为start >= str.length

关键代码

public List<String> letterCombinations(String digits) {
  List<String> resultList = new ArrayList<>();
  if (digits == null || digits.length() == 0) {
    return resultList;
  }
  Map<Character, String> map = new HashMap<>();
  map.put('2', "abc");
  map.put('3', "def");
  map.put('4', "ghi");
  map.put('5', "jkl");
  map.put('6', "mno");
  map.put('7', "pqrs");
  map.put('8', "tuv");
  map.put('9', "wxyz");

  // 选择列表
  StringBuilder sb = new StringBuilder();
  int start = 0;
  trackBackFunction(digits, resultList, start, sb, map);
  return resultList;
}

private void trackBackFunction(String digits, List<String> resultList, int start, StringBuilder sb, Map<Character, String> map) {
  if (start == digits.length()) {
    resultList.add(sb.toString());
    return;
  }

  String selectList = map.get(digits.charAt(start));

  for (int i = 0; i < selectList.length(); i++) {
    sb.append(selectList.charAt(i));
    // 需要注意的是这里需要start + 1或者 ++start， 而不能用start++
    trackBackFunction(digits, resultList, start + 1, sb, map);
    sb.deleteCharAt(sb.length() - 1);
  }
}