[回溯算法]leetcode17. 电话号码的字母组合(c实现)
【摘要】 题目给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母示例 1:输入:digits = “23”输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]示例 2:输入:digits = “”输出:[]示例 3:输入:digits = “2...
题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母
示例 1:
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2:
输入:digits = “”
输出:[]
示例 3:
输入:digits = “2”
输出:[“a”,“b”,“c”]
代码
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char*path;
int pathTOP;
char**result;
int resultTOP;
char*letterMap[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void backtracking(char *digits,int index)//index记录数字位置
{
int i=0;
//递归终止条件
if(index==strlen(digits))//纵向的递归次数与数字个数相同
{
char*temp=(char*)malloc(sizeof(char)*strlen(digits)+1);//+1 是因为字符串结尾以'\0'
for(i=0;i<strlen(digits);i++)
{
temp[i]=path[i];
}
temp[strlen(digits)]= '\0';//最后的位置加上'\0'
result[resultTOP++]=temp;
return ;
}
int digit=digits[index]-'0';//digit代表真正的数字
char*letter=letterMap[digit];//letter代表数字所对应的字符串
for(i=0;i<strlen(letter);i++)
{
path[pathTOP++]=letter[i];
//递归
backtracking(digits,index+1);//index+1为下一个数字
//回溯
pathTOP--;
}
}
char ** letterCombinations(char * digits, int* returnSize){
path=(char*)malloc(sizeof(char)*strlen(digits));
result=(char*)malloc(sizeof(char*)*300);
*returnSize=0;
if(strlen(digits)==0)
{
return NULL;
}
pathTOP=0;
resultTOP=0;
backtracking(digits,0);
*returnSize=resultTOP;
return result;
}
#过程分析
1.图片演示
2.index的作用
不同于组合问题中的startindex,因为组合问题是属于在一个集合中进行的
在每次取值时,集合中可选的数变少
而该题处于两个或两个以上的集合联系起来的,index记录数字的位置的下标
如 : “23”
题中所给的digits为字符串记录数字
index默认为0,digits[index] 即 digits[0]=2 digits[1]=3
3. -'0’的原因
因为我们是通过字符串来传递数字的,所以通过-‘0’,来获取当前所处真正的数字,
而每个数字都对应相应地的字符串,如:2对应 “abc”
for循环以当前所处字符串的大小作为边界,
递归时,传入下一个数字作为index
4. 部分递归图
当digits="23"时,以ad为例
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)