LeetCode 面试经典 150_回溯_电话号码的字母组合（98_17_C++_中等）

题目描述：

给定一个仅包含数字 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 键则从 [a,b,c] 中选取一个字母，第二次按的是 7 键，则从 [p,q,r,s] 中选取一个字母，以此类推。最后将选出的字母按照顺序依次进行组合，就是电话号码的字母组合。为了能快速的得到数字与字母的对应关系，我们需将其关系存入哈希表。（不定次数的多重循环转换为递归问题）

2、复杂度分析：
① 时间复杂度：O(3^m*4ⁿ)，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n 是输入数字的总个数(可转换为多重循环问题进行理解)。

② 空间复杂度：O(m+n)，递归需要 m+n空间（每层挑选一个字母），哈希表为固定的常熟O(1)。

代码实现

代码实现（思路一（递归（回溯）））：

classSolution{private://存储号码与字母的对应关系unordered_map<char,string>map;//记录一种电话号码的字母组合vector<char>path;//存储所有的电话号码字母组合vector<string>ans;//创建号码与字母的对应关系voidcreateMap(){map['2']="abc";map['3']="def";map['4']="ghi";map['5']="jkl";map['6']="mno";map['7']="pqrs";map['8']="tuv";map['9']="wxyz";}voidbacktracking(string digits,intn){//当一个组合中字母数量达到要求是存储到ans中if(path.size()==digits.size()){//将char类型的path进行拼接装入ansans.emplace_back(string(path.begin(),path.end()));return;}//str代表当前号码对应的字母string str=map[digits[n]];for(inti=0;i<str.size();i++){//将字母存入path中path.emplace_back(str[i]);//挑选下一个号码对应的字母backtracking(digits,n+1);//回溯path.pop_back();}}public:vector<string>letterCombinations(string digits){//清空ans和path，防止上次调用残留数据ans.clear();path.clear();//如果未输入号码则返回 []if(digits=="")returnans;//创建号码与字母的对应关系createMap();//电话号码的字母组合backtracking(digits,0);returnans;}};

以思路一为例进行调试

#include<iostream>#include<vector>#include<unordered_map>usingnamespacestd;classSolution{private://存储数字与字母的对应关系unordered_map<char,string>map;//记录一种电话号码的字母组合vector<char>path;//存储所有的电话号码字母组合vector<string>ans;//创建数字与字母的对应关系voidcreateMap(){map['2']="abc";map['3']="def";map['4']="ghi";map['5']="jkl";map['6']="mno";map['7']="pqrs";map['8']="tuv";map['9']="wxyz";}voidbacktracking(string digits,intn){//当一个组合中字母数量达到要求是存储到ans中if(path.size()==digits.size()){//将char类型的path进行拼接装入ansans.emplace_back(string(path.begin(),path.end()));return;}//str代表当前号码对应的字母string str=map[digits[n]];for(inti=0;i<str.size();i++){//将字母存入path中path.emplace_back(str[i]);//挑选下一个号码对应的字母backtracking(digits,n+1);//回溯path.pop_back();}}public:vector<string>letterCombinations(string digits){//清空ans，防止上次调用残留数据ans.clear();//如果未输入号码则返回 []if(digits=="")returnans;//创建号码与字母的对应关系createMap();//电话号码的字母组合backtracking(digits,0);returnans;}};intmain(intargc,charconst*argv[]){string digits="23";//电话号码的字母组合Solution s;vector<string>ans=s.letterCombinations(digits);//输出电话号码的字母组合for(constauto&i:ans){cout<<i<<" ";}return0;}

部分代码解读

string(path.begin(),path.end())

vector<char>path;string(path.begin(),path.end())

这个方法通常用于将其他容器（例如 std::vector 或 std::deque）转换为 std::string。它将指定范围内的字符拷贝到新的 std::string 中。

LeetCode 面试经典 150_回溯_电话号码的字母组合（98_17)原题链接
欢迎大家和我沟通交流(✿◠‿◠)