【Leetcode】17、电话号码的字母组合
题目：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题思路：
通过回溯法遍历所有的字母组合，先建立数字和字母的对应关系，处理边界情况，并计算左右组合数，再通过回溯算法生成所有组合，最后收集结果并返回。
代码解释：
digits: 输入的数字字符串；
index: 当前处理的数字索引；
current: 当前已生成的组合；
result: 存储所有结果的数组；
returnSize: 结果的数量；
代码：
const char *digitMap[] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9
};
void backtrack(const char *digits, int index, char *current, char **result, int *returnSize) {if(digits[index]=='\0') {result[*returnSize]=(char*)malloc(strlen(current)+1);strcpy(result[*returnSize],current);(*returnSize)++;return;}int digit=digits[index]-'0';const char* letters=digitMap[digit];for(int i=0;letters[i]!='\0';i++) {current[index]=letters[i];current[index+1]='\0';backtrack(digits,index+1,current,result,returnSize);}
}
int calculateTotalCombinations(const char *digits) {if(digits[0]=='\0') return 0;int total=1;for(int i=0;digits[i]!='\0';i++) {int digit=digits[i]-'0';int len=strlen(digitMap[digit]);total*=len;}return total;
}
char **letterCombinations(const char *digits, int *returnSize) {*returnSize=0;if (digits==NULL||digits[0]=='\0') return NULL;int total=calculateTotalCombinations(digits);char** result=(char**)malloc(total*sizeof(char*));if(result==NULL) return NULL;int digitsLen=strlen(digits);char* current=(char*)malloc((digitsLen+1)*sizeof(char));if(current==NULL) {free(result);return NULL;}current[digitsLen]='\0';backtrack(digits,0,current,result,returnSize);free(current);return result;
}