力扣题库电话号码的字母组合-创新互联
寒假算法学习与练习
每日一题
当前标题:力扣题库电话号码的字母组合-创新互联
URL链接:http://myzitong.com/article/dhehgp.html
电话转字母
创新互联公司专注于梅里斯企业网站建设,成都响应式网站建设公司,商城系统网站开发。梅里斯网站建设公司,为梅里斯等地区提供建站服务。全流程按需求定制开发,专业设计,全程项目跟踪,创新互联公司专业和态度为您提供的服务题目描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。力扣
对于这道题想到的第一步是使用键值对,将数字对应到一个一个字符,想的是将字符都放在列表中,然后遍历digit,把每一个数字对应的列表列出来,然后来进行排列组合,这样的方法会使时间复杂度大大增大。作为菜鸡的我,去看了看大佬的解题方法,实现使用键值对,这个想法是对的,就是后面的处理,想的太复杂了,该题使用回溯法,大大降低了时间复杂度。
学习一下回溯法的基本思想
回溯法基本思想:
就是列出所有情况,然后用深度优先搜索解空间树(就是列出所有结果),回溯就是回到父节点,去往另外一个子节点。这里就不过多赘述了。
该题回溯思想:
解空间树:
代码:
void backtrack(vector&result,const unordered_map&phonemap,const string &digits,int index,string&combination)
{
if(index==digits.length())
{
result.push_back(combination);
}
else{
char digit=digits[index];
const string &letters=phonemap.at(digit);
for(const char&letter:letters)
{
combination.push_back(letter);//第一个字母
backtrack(result,phonemap,digits,index+1,combination);//往下
combination.pop_back();//下一个字母
}
}
}
vectorletterCombinations(string digits) {
vectorresult;
if(digits.empty())
{
return result;
}
unordered_mapsymbolValues={
{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jk"},
{'6',"mno"},
{'7',"pqrs"},
{'8',"tuv"},
{'9',"wxyz"},
};
string combination;
backtrack(result,symbolValues,digits,0,combination);
return result;
}
代码解释
主体函数就是backtrack函数,传入的值分别是最后结果列表、键值对、数字列表、第几层(我理解是解空间树的第几层,也就是第几个数字),combination就是数字对应的每一个字母(2:abc)
用一个具体例子来解释代码运行过程,以23为例子
写的可能不是很清楚,我是这样一步一步走代码,理解代码的意思,实在是太菜了,只能先看懂别人的代码和思想,再继续前进。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前标题:力扣题库电话号码的字母组合-创新互联
URL链接:http://myzitong.com/article/dhehgp.html