C++ 电话号码的字母组合功能实现

目录

• 电话号码的字母组合
• 描述
• 示例1
• 示例2
• 示例3
• 思路/解法
• 方式一
• 方式二

电话号码的字母组合

描述

给定一个仅包含数字 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'] 的一个数字。

思路/解法

方式一

回溯算法，在当前题目非常适合。先使用map容器记录所有可能，在回溯遍历即可。

class Solution {
public:
    void TrackBack(string& digits,int charStart,int size,string& back,vector<string>& res,std::unordered_map<char,string>& maps)
    {
        if(back.length() == size)
        {
            res.push_back(back);
            return;
        }
        int length = maps[digits[charStart]].length();
        std::string str = maps[digits[charStart]];
        for(int i = 0;i < length; i++)
        {
            back.push_back(str[i]);
            TrackBack(digits,charStart + 1,size,back,res,maps);
            back.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> arrs;
        if(digits == "")
            return arrs;
        std::unordered_map<char,string> maps{{'2',"abc"},{'3',"def"},{'4',"ghi"},
        {'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        string back;
        TrackBack(digits,0,digits.length(),back,arrs,maps);
        return arrs;
    }
};

方式二

递归法，使用递归求解出所有的可能性并合并结果即可。

class Solution {
public:
    vector<string> CharCombine(string digits,unordered_map<char,string>& maps)
    {
        vector<string> tmp;
        int length = digits.size();
        //边界条件（当长度为0或1时直接跳出）
        if(1 == length)
        {
            string str = maps[digits[0]];
            for(int j = 0;j < str.length();j++)
            {
                string s = "";
                tmp.push_back(s.append(1,str[j]));
            }
            return tmp;
        }
        else if(0 == length)
            return tmp;
        else//递归
        {
            string str = maps[digits[length-1]];
            vector<string> res = CharCombine(digits.substr(0,length-1),maps);
            for(int i = 0;i < str.length();i++)
            {
                for(int j = 0;j < res.size();j++)
                {
                    string t = res[j];
                    tmp.push_back(t.append(1,str[i]));
                }
            }
            return tmp;
        }
    }

    vector<string> letterCombinations(string digits) {
        std::unordered_map<char,string> maps{{'2',"abc"},{'3',"def"},{'4',"ghi"},
        {'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        return CharCombine(digits,maps);
    }
};

到此这篇关于C++ 电话号码的字母组合的文章就介绍到这了,更多相关C++ 电话号码的字母组合内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！