LeetCode 热题 100_电话号码的字母组合（57_17_中等

LeetCode 热题 100_电话号码的字母组合（57_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 键则从 [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)。

代码实现

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

class Solution {
private://存储号码与字母的对应关系unordered_map<char,string> map;//记录一种电话号码的字母组合vector<char> path;//存储所有的电话号码字母组合vector<string> ans;//创建号码与字母的对应关系void createMap(){map['2']="abc";map['3']="def";map['4']="ghi";map['5']="jkl";map['6']="mno";map['7']="pqrs";map['8']="tuv";map['9']="wxyz";}void backtracking(string digits,int n){//当一个组合中字母数量达到要求是存储到ans中if(path.size()==digits.size()){//将char类型的path进行拼接装入ansans.emplace_back(string(path.begin(),path.end()));return;}//str代表当前号码对应的字母string str=map[digits[n]];for (int i = 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=="") return ans;//创建号码与字母的对应关系createMap();//电话号码的字母组合backtracking(digits,0);return ans;}
};

以思路一为例进行调试

#include<iostream>
#include <vector>
#include<unordered_map>
using namespace std;class Solution {
private://存储数字与字母的对应关系unordered_map<char,string> map;//记录一种电话号码的字母组合vector<char> path;//存储所有的电话号码字母组合vector<string> ans;//创建数字与字母的对应关系void createMap(){map['2']="abc";map['3']="def";map['4']="ghi";map['5']="jkl";map['6']="mno";map['7']="pqrs";map['8']="tuv";map['9']="wxyz";}void backtracking(string digits,int n){//当一个组合中字母数量达到要求是存储到ans中if(path.size()==digits.size()){//将char类型的path进行拼接装入ansans.emplace_back(string(path.begin(),path.end()));return;}//str代表当前号码对应的字母string str=map[digits[n]];for (int i = 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=="") return ans;//创建号码与字母的对应关系createMap();//电话号码的字母组合backtracking(digits,0);return ans;}
};int main(int argc, char const *argv[])
{string digits="23";//电话号码的字母组合Solution s;vector<string> ans=s.letterCombinations(digits);//输出电话号码的字母组合for (const auto &i : ans){cout<<i<<"  ";}return 0;
}

部分代码解读

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

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

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

LeetCode 热题 100_电话号码的字母组合（57_17)原题链接
欢迎大家和我沟通交流(✿◠‿◠)