LeetCode 热题 100_电话号码的字母组合 （57_17_中等_C++）(string(path.begin(),path.end()))

题目描述：

给定一个仅包含数字 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进行拼接装入ans
            ans.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进行拼接装入ans
            ans.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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)