资讯详情

 归类：回溯算法

回溯三部曲：

1.确定回溯函数参数

首先需要一个字符串s来收集叶子节点的结果，然后用一个字符串数组result来保存起来，这两个变量依然定义为全局。

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

index是用来记录遍历第几个数字了，就是用来遍历digits的，同时index也表示树的深度。

vector<string> result;
string s;
void backtracking(const string& digits, int index)

2.确定终止条件

叶子节点是用来收集的结果集，终止条件就是如果index等于输入的数字个数(digits.size)了，index是用来遍历digits的，然后收集结果，结束

本层递归。

if (index == digits.size()) {result.push_back(s);return;
}
3.确定单层遍历逻辑
首先取index指向的数字，并找到对应的字符集
然后for循环来处理这个字符集

int digit = digits[index] - '0';        // 将index指向的数字转为int
string letters = letterMap[digit];      // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了s.pop_back();                       // 回溯
}

class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if (index == digits.size()) {result.push_back(s);return;}int digit = digits[index] - '0';        // 将index指向的数字转为intstring letters = letterMap[digit];      // 取数字对应的字符集for (int i = 0; i < letters.size(); i++) {s.push_back(letters[i]);            // 处理backtracking(digits, index + 1);    // 递归，注意index+1，一下层要处理下一个数字了s.pop_back();                       // 回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};