微信手机网站开发,国内永久免费crm系统z,芜湖网站优化,安徽安庆地图题型#xff1a;映射、回溯算法、递归
链接#xff1a;17. 电话号码的字母组合 - 力扣#xff08;LeetCode#xff09;
来源#xff1a;LeetCode
题目描述
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出…题型映射、回溯算法、递归
链接17. 电话号码的字母组合 - 力扣LeetCode
来源LeetCode
题目描述
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 题目样例
示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
题目思路
因为题目给的长度是0—4所以纯暴力也可以极限情况4个for循环
这种循环次数自己也不知道会多少次可以考虑用递归遍历完一个点的所有情况在遍历下一个点。这种思想是一种回溯的思想
举个例子比如说数字是【646345】在遍历完第一个元素【6】对应的字母【m、n、o】后就继续遍历【4】的字母【g、h、i】
至于【数字-字母】映射表为了避免 数字 和 字符串之间的类型转化可以用一个unordered_mapstring,string来实现映射表
C代码
class Solution {vectorstring ans;// 建立映射表unordered_mapstring, string hash {{2, abc}, {3, def}, {4, ghi}, {5, jkl},{6, mno}, {7, pqrs}, {8, tuv}, {9, wxyz}};void huisu(const string digits,int index,const string s)//digits是数字 s是要被添加的字母{//递归结束条件if(index digits.size()){ans.emplace_back(s);return;}string digit(1,digits[index]);//当前进行遍历的字母将char转化为string类型string letters hash[digit];for(auto c : hash[digit]){// 非const左值引用得让形参中的临时string变成const string引用huisu(digits,index 1,s c);}}public:vectorstring letterCombinations(string digits) {if(digits.length() 0)return ans;string addstr ;huisu(digits,0,addstr);//从0开始递归return ans;}
};
结算页面
