Day130 | 灵神 | 回溯算法 | 子集型 电话号码的字母组合

Day130 | 灵神 | 回溯算法 | 子集型 电话号码的字母组合

17.电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

思路：

笔者用index代替i，这里的index其实就是digits数组的下标

按照灵神的回溯三问，那就是

1.当前的操作：找到本层要给path[index]里面填入哪个字母，很明显的是每层就是一个数字的那几个字母，所以就是选定一个数字然后从它的字母中选一个

2.子问题：构造字符串>=index的部分，其实也就是说明经过了index层选择之后，我们已经确定了i位字母

3.下一个子问题：构造字符串>=index+1的部分，就是说明我们下一层的递归参数是index+1，因为我们已经在本层的字母中选择了一个，所以要继续往下走了，表现在数组上就是继续往下遍历digits

注意的细节：

映射的建立，下标要对上数字，也就是让映射的数组从下标2开始而不是0，这样会方便很多

完整代码：

class Solution {
public:vector<string> res;vector<string> s{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void backtracking(string digits,string path,int index){if(index==digits.size()){res.push_back(path);return ;}int n=(int)(digits[index]-'0');for(int i=0;i<s[n].size();i++){path.push_back(s[n][i]);backtracking(digits,path,index+1);path.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0)return res;string path;backtracking(digits,path,0);return res;}
};

灵神代码：

灵神没有"恢复现场"这一步，是因为灵神把path初始化为全0的字符串，并且在递归中直接覆盖了对应的值，而恰巧字符串返回时的长度全都是digits数组的长度，所以把path放入结果集的时候肯定path数组都会被覆盖一遍

class Solution {const string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public:vector<string> letterCombinations(string digits) {int n = digits.length();if (n == 0) {return {};}vector<string> ans;string path(n, 0); // 注意 path 长度一开始就是 n，不是空串auto dfs = [&](this auto&& dfs, int i) {if (i == n) {ans.emplace_back(path);return;}for (char c : MAPPING[digits[i] - '0']) {path[i] = c; // 直接覆盖dfs(i + 1);}};dfs(0);return ans;}
};