目录电话号码的字母组合描述示例1示例2示例3思路/解法方式一方式二电话号码的字母组合 描述 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入:digits = ""
输出:[]
输入: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++ 电话号码的字母组合内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C++ 电话号码的字母组合功能实现
本文链接: https://www.lsjlt.com/news/172034.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0