C语言给定一个仅包含数字 2-9 的字符串,返回所有它在手机键盘上能表示的字母组合

这是一道常见的回溯算法问题。我们可以先建立一个数字到字母的映射表，然后使用回溯算法枚举所有可能的字母组合。

以下是示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 数字到字母的映射表
const char *map[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

void backtrack(char **result, char *digits, int index, char *buffer) {
    if (digits[index] == '\0') {
        // 找到一个合法的组合，将其添加到结果数组中
        result[0] = (char *)realloc(result[0], (strlen(result[0]) + strlen(buffer) + 1) * sizeof(char));
        strcat(result[0], buffer);
        return;
    }
    
    int num = digits[index] - '0';
    const char *letters = map[num];
    int len = strlen(letters);
    
    for (int i = 0; i < len; i++) {
        buffer[index] = letters[i];
        backtrack(result, digits, index + 1, buffer);
    }
}

char **letterCombinations(char *digits, int *returnSize) {
    if (digits == NULL || *digits == '\0') {
        // 如果输入字符串为空，则返回空结果
        *returnSize = 0;
        return NULL;
    }
    
    // 计算结果数组的长度
    int len = 1;
    for (char *p = digits; *p != '\0'; p++) {
        int num = *p - '0';
        len *= strlen(map[num]);
    }
    
    // 初始化结果数组
    char **result = (char **)malloc(sizeof(char *));
    result[0] = (char *)malloc(sizeof(char));
    result[0][0] = '\0';
    
    // 递归计算所有组合
    char *buffer = (char *)malloc((strlen(digits) + 1) * sizeof(char));
    buffer[strlen(digits)] = '\0';
    backtrack(result, digits, 0, buffer);
    free(buffer);
    
    // 返回结果数组和长度
    *returnSize = len;
    return result;
}

int main() {
    char *digits = "23";
    int size;
    char **result = letterCombinations(digits, &size);
    for (int i = 0; i < size; i++) {
        printf("%s\n", result[i]);
    }
    return 0;
}

运行结果为：

ad
ae
af
bd
be
bf
cd
ce
cf