[回溯算法]leetcode17. 电话号码的字母组合(c实现)
source link: https://blog.51cto.com/u_15787387/5844016
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[回溯算法]leetcode17. 电话号码的字母组合(c实现)
精选 原创给定一个仅包含数字 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为例
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK