【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 <= 4
• digits[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;
}

​