寒假算法学习与练习
每日一题
电话转字母
创新互联公司专注于梅里斯企业网站建设,
成都响应式网站建设公司,
商城系统网站开发。梅里斯网站建设公司,为梅里斯等地区提供建站服务。全流程按需求定制开发，专业设计，全程项目跟踪，
创新互联公司专业和态度为您提供的服务
题目描述：给定一个仅包含数字 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元起，快前往官网查看详情吧
当前文章：力扣题库电话号码的字母组合-创新互联
浏览路径：
http://cdkjz.cn/article/dhehgp.html
