(回溯) LeetCode 17. 电话号码的组合

原题链接

一. 题目描述

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 <= 4
• digits[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)

喜欢的话给个关注吧！！