在重庆_那里可以做诚信网站认证,建站管理后台,刚做的win7系统连上网站没网,佛山建站专家原题链接
一. 题目描述
17. 电话号码的字母组合
已解答
中等
相关标签
相关企业
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对…原题链接
一. 题目描述
17. 电话号码的字母组合
已解答
中等
相关标签
相关企业
给定一个仅包含数字 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] 的一个数字。
二. 解题思路
本题意思是给你一个由1到9数字组成的字符串每一个数组都对应了九宫格上的一个位置每一个位置上面都有相对应的字母让你求出给定的数字字符串所对应的字母的所有组合情况我们来举个栗子 这是代码随想录中的一个例子搬运工。
通过上面的例子我们可以看出这个和前面所做到的组合其实差不多就是多了个数字和字母相对应的情况
1. 我们首先得构造一个字符串数组用来存储每一个数字和它对应的所有字母的映射关系。
2. 用字符串s 记录当前的组合字符串数组res 记录结果然后开始递归回溯
3. 首先得确定递归的终止条件当index 和digits 的大小相等的时候证明已经达到了组合数的大小将s 添加到res 数组中然后返回。
4. 然后通过index 找出下一个组合的数字digit 通过字符串数组lettermap 的映射关系找出相对应的字符串letter 然后开始遍历
5. 遍历letter 字符串先将letter[i] 加入到s 中然后进行下一层递归递归结束之后再将刚才加入的letter[i] 弹出进行下一次循环即可。
注意在执行递归的前提是带判断digits 是否为空如果为空就直接进行输出即可不用进行递归。
三. 代码
class Solution {
public:string lettermap[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};string s;vectorstring res;void back(string digits, int index){if(index digits.size()){res.push_back(s);return;}int digit digits[index] - 0;string letter lettermap[digit];for(int i 0; i letter.size(); i){s.push_back(letter[i]);back(digits, index 1);s.pop_back();}}vectorstring letterCombinations(string digits) {if(digits.size() 0){return res;}back(digits, 0);return res;}
};
四. 总结
本题也是一道训练递归好题目建议练习
时间复杂度O(N∗M)
空间复杂度O(N∗M)
喜欢的话给个关注吧
