leetcode刷题-[17]电话号码的字母组合

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

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

leetcode刷题-[17]电话号码的字母组合

示例 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);
  }
}
上一篇:获取格式化查询字符串


下一篇:15. 三数之和