|
今天做到?电话号码的字母组合这道题，这种其实就是穷举的暴力解法。将所有的组合，排列都列举出来，第一次想的方法就是用for循环，但是是数字不定的举例，所有得用回溯和递归来解决。关于回溯与递归，这篇文章写得特别清楚代码随想录，?在这再说一次大佬真的特别牛！如果文字还不够清楚，可以看看大佬出的视频这里就不在赘述了。
（在看题解的过程中时，可以几份题解一起对照参考，每份题解都有着不同的具体实现，最主要的是提取出自己的东西）
以下附上自己的解题心得?与思路。
class Solution {
public:
void backTrack(int index,const string& digits,vector<string>& combinations,string& combination,const unordered_map<char,string>& phoneMap) {
//终止条件
if(index == digits.length()) {
combinations.push_back(combination);//将最后得到的叶子节点添加到结果的集合中
}
else{
//如果不是叶子节点就继续做
char digit = digits[index]; //第一次将"23"里面的'2'拿出来
const string& letters = phoneMap.at(digit); //设立一个中间变量letters 拿到'2'里面的"abc"
//每次从"abc"里面拿出一个出来。对每个进行操作
for(const char& letter:letters) {
combination.push_back(letter); //此时的 combination=='a'
backTrack(index + 1, digits, combinations, combination, phoneMap);//递归的调用回溯算法。 第二次调用就是 '3'拿出来得到"def" 对d来说，此时得到"ad"
combination.pop_back();//此时将得到的"ad"的d移出，不然会累计在一起。
}
}
}
vector<string> letterCombinations(string digits) {
vector<string> combinations;
//判断是否为空 若为空直接返回
if(digits.empty()) {
return combinations;
}
unordered_map<char,string> phoneMap={
{'2',"abc"},
{'3',"def"},
{'4',"ghi"},
{'5',"jkl"},
{'6',"mno"},
{'7',"pqrs"},
{'8',"tuv"},
{'9',"wxyz"}
};
string combination;
backTrack(0,digits,combinations,combination,phoneMap);
return combinations;
}
};
其实在实际写代码的时候，我疑惑的就是需要什么变量，我的参数列表应该写什么东西。而且在思考问题的时候，往往不可能一次性得到最好的解法。（目前自己想法就是先在里面写，需要什么变量就再添加上去，不要想着一次性添加完成，不停地查缺补漏，主要是逻辑够清楚）
大家共勉，也希望大佬看了给点建议~~
|