前文
C++深度递归遍历解决"电话号码的字母组合问题",本题考察的比较全面,考察到 vector的使用,深度遍历以及递归的熟练度,希望能对铁子们有所帮助
一,题目
链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
二,解法
如上图所示,以"256"为例,我们将三个字符串各个字符的排列组合展开,我们发现这个结构类似于多叉树的结构,主要是考察深度遍历,因此我们也可以用递归来完成。
既然已经确定可以用递归来完成,那么我们就需要确定递归所需参数。
首先我们需要创建一个 vector<string> ret用来 存储需要返回的字母组合,同时需要创建 size_t depth来 控制递归的深度,再创建一个 string combinestr用来 存储每组的字母组合,当然digits也是必须要传的。
所需参数已确定,那么具体的递归过程呢。文章来源:https://www.toymoban.com/news/detail-412295.html
我们以上图"ajm" "ajn" "ajo"为例子,具体讲解一下递归的过程
三,代码
代码实现:文章来源地址https://www.toymoban.com/news/detail-412295.html
class Solution {
//获取每个数字对应字符串
//由于0 1没字符,所以设置成空串
string get_numberstr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
void Combination(const string& digits,size_t depth,string combinestr, vector<string>& ret)
{
//depth控制深度,digits的长度就是我们递归的深度
if(depth==digits.size())
{
ret.push_back(combinestr);
return;
}
int digit=digits[depth]-'0';//获取数字字符
string numberstr=get_numberstr[digit];//获取数字所对应的字符串
for(auto ch:numberstr)
{
Combination(digits,depth+1,combinestr+ch,ret);
}
}
vector<string> letterCombinations(string digits) {
vector<string> ret;
if(digits.size()==0)
{
return ret;
}
size_t depth=0;//控制递归深度
string combinestr;//存储每组字符串
Combination(digits,depth,combinestr,ret);
return ret;
}
};
成功实现
到了这里,关于17.电话号码的字母组合(深度递归遍历解决经典老题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!