C++ 电话号码的字母组合功能实现
短信预约 -IT技能 免费直播动态提醒
电话号码的字母组合
描述
给定一个仅包含数字 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++ 电话号码的字母组合内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
