LeetCode-电话号码的字母组合（C++）_leetcode 电话号码的字母组合c++

17. 电话号码的字母组合

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

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

示例 1：

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

思路：用回溯算法，首先定义一个数字到字母的映射letterMap，然后定义两个全局变量，result表示结果集，path表示收集到的字母组合。

确定回溯函数的参数，数字组合digits以及表示当前是第几个数字的index。

终止条件就是index等于digits的大小，然后将path加入结果接，return。

单层回溯逻辑：将digits[index]转换成数字，将数字对应的字符串保存下来letters，for循环横向遍历就是将当前数字对应的所有字母都遍历，for循环内，将当前字母加入path，递归处理下一个数字，然后回溯，将之前加入的字母弹出。

代码：

class Solution {	//17. 电话号码的字母组合
public:
	const string letterMap[10] = {"", "",  "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
	vector<string> result;
	string path;
	void backtracking(const string& digits, int index) {
		if (index == digits.size()) {
			result.push_back(path);
			return;
		}
		int digit = digits[index] - '0';
		string letters = letterMap[digit];
		for (int i = 0; i < letters.size(); ++i) {
			path.push_back(letters[i]);
			backtracking(digits, index + 1);
			path.pop_back();
		}
	}
	vector<string> letterCombinations(string digits) {
		if (digits.size() == 0)return result;
		backtracking(digits, 0);
		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

参考资料：代码随想录