伊春住房和城乡建设网站百度广告费一般多少钱
原题链接
一. 题目描述
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;vector<string> 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();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0){return res;}back(digits, 0);return res;}
};四. 总结
本题也是一道训练递归好题目，建议练习
时间复杂度：O(N∗M)
空间复杂度：O(N∗M)