宣城老品牌网站建设,南通智能模板建站,装饰设计公司资质,大同格泰网站建设Day130 | 灵神 | 回溯算法 | 子集型 电话号码的字母组合
17.电话号码的字母组合
17. 电话号码的字母组合 - 力扣#xff08;LeetCode#xff09;
思路#xff1a; 笔者用index代替i#xff0c;这里的index其实就是digits数组的下标
按照灵神的回溯三问#xff0c;那就…Day130 | 灵神 | 回溯算法 | 子集型 电话号码的字母组合
17.电话号码的字母组合
17. 电话号码的字母组合 - 力扣LeetCode
思路 笔者用index代替i这里的index其实就是digits数组的下标
按照灵神的回溯三问那就是
1.当前的操作找到本层要给path[index]里面填入哪个字母很明显的是每层就是一个数字的那几个字母所以就是选定一个数字然后从它的字母中选一个
2.子问题构造字符串index的部分其实也就是说明经过了index层选择之后我们已经确定了i位字母
3.下一个子问题构造字符串index1的部分就是说明我们下一层的递归参数是index1因为我们已经在本层的字母中选择了一个所以要继续往下走了表现在数组上就是继续往下遍历digits
注意的细节
映射的建立下标要对上数字也就是让映射的数组从下标2开始而不是0这样会方便很多
完整代码
class Solution {
public:vectorstring res;vectorstring s{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};void backtracking(string digits,string path,int index){if(indexdigits.size()){res.push_back(path);return ;}int n(int)(digits[index]-0);for(int i0;is[n].size();i){path.push_back(s[n][i]);backtracking(digits,path,index1);path.pop_back();}}vectorstring 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:vectorstring letterCombinations(string digits) {int n digits.length();if (n 0) {return {};}vectorstring 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;}
};
