【回溯算法】leetcode 17. 电话号码的字母组合

17. 电话号码的字母组合

题目描述

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

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

示例1：

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

示例2：

输入： digits = “”
输出： []

示例3：

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

提示

• $0<=digits.length<=4$
• $digits[i]是范围{[}^{\prime }{2}^{\prime }{,}^{\prime }{9}^{\prime }]的一个数字。$

方法：回溯算法

解题思路

这里定义一个字符串数组用来将数字映射到对应的字母。

const string letterMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
1

回溯三部曲：

• 确定回溯函数参数
  首先需要一个字符串 path 来收集叶子结点的结果，然后用一个字符串数组 result 来收集所有结果。这两个变量定义为全局。

  再来看参数，参数指定是有题目中给的 string digits，然后还要有一个参数就是 int 型的 index。

  这个 index 是记录遍历第几个数字了，就是用来遍历 digits 的（题目中给出数字字符串），同时 index 也表示树的深度。

  const string letterMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  vector<string> result;
  string path;
  void dfs(int index, const string& digits)
  1
  2
  3
  4

• 确定终止条件
  终止条件就是如果 index 等于 输入的数字个数（digits.size）了（本来index 就是用来遍历 digits 的）。然后收集结果，结束本层递归。

  	if(index == digits.size()) {
          result.push_back(path);
          return;
      };
  1
  2
  3
  4

• 确定单层遍历逻辑
  首先要取 index 指向的数字，并找到对应的字符集（手机键盘的字符集）。本题每一个数字代表的是不同集合，也就是求不同集合之间的组合。然后 for 循环来处理这个字符集，代码如下：

  	int digit = digits[index] - 48;
      string letters = letterMap[digit];
      for(int i = 0; i < letters.size(); i++) {
          path.push_back(letters[i]);
          dfs(index + 1, digits);
          path.pop_back();
      }
  1
  2
  3
  4
  5
  6
  7

代码

class Solution {
public:
    const string letterMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> result;
    string path;
    void dfs(int index, const string& digits) {
        if(index == digits.size()) {
            result.push_back(path);
            return;
        };
        int digit = digits[index] - 48;
        string letters = letterMap[digit];
        for(int i = 0; i < letters.size(); i++) {
            path.push_back(letters[i]);
            dfs(index + 1, digits);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)  return result;
        dfs(0, digits);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24