隐式回溯
- 当path作为dfs函数传入的时候,不用显式回溯(push_back,pop), 因为函数return后, 会自动把加的这一位去掉
// y总代码
class Solution {
public:
vector<string> ans;
string strs[10] = {
"", "", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz",
};
vector<string> letterCombinations(string digits) {
if (digits.empty()) return ans;
dfs(digits, 0, "");
return ans;
}
void dfs(string &digits, int u, string path) {
if (u == digits.size()) ans.push_back(path);
else {
for (auto c : strs[digits[u] - '0']) {
dfs(digits, u + 1, path + c);
}
}
}
};
显式回溯
- 把index还有path设置成全局变量,dfs函数每一次递归调用的时候 需要手动修改path 和 index 然后调用结束之后再手动恢复现场
// 显式回溯
class Solution {
public:
vector<string> ans;
string strs[10] = {
"", "", "abc", "def",
"ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz",
};
int index = 0;
string path;
vector<string> letterCombinations(string digits) {
if (digits.empty()) return ans;
dfs(digits);
return ans;
}
void dfs(string &digits) {
if (path.size() == digits.size()) ans.push_back(path);
else {
for (auto c : strs[digits[index] - '0']) {
path.push_back(c);
index ++;
dfs(digits);
path.pop_back();
index --;
}
}
}
};