C语言编程--14.电话号码的字母组合

题目：

给定一个仅包含数字 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’] 的一个数字。

代码：

（1）蛮力法：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** Note: The returned array must be malloced, assume caller calls free().*/
char** letterCombinations(char* digits, int* returnSize) {char data[8][5] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};*returnSize = 0;int len = strlen(digits);if (len == 0) {return NULL;}// 计算最大可能的组合数int maxCombinations = 1;for (int i = 0; i < len; i++) {if (digits[i] == '7' || digits[i] == '9') {maxCombinations *= 4;} else {maxCombinations *= 3;}}// 动态分配结果数组的内存char **result = (char **)malloc(maxCombinations * sizeof(char *));for (int i = 0; i < maxCombinations; i++) {result[i] = (char *)malloc((len + 1) * sizeof(char));result[i][0] = '\0';}if (len == 1) {char *letters = data[digits[0] - '2'];for (int i = 0; letters[i] != '\0'; i++) {result[*returnSize][0] = letters[i];result[*returnSize][1] = '\0';(*returnSize)++;}} else if (len == 2) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = '\0';(*returnSize)++;}}} else if (len == 3) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];char *letters3 = data[digits[2] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {for (int k = 0; letters3[k] != '\0'; k++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = letters3[k];result[*returnSize][3] = '\0';(*returnSize)++;}}}} else if (len == 4) {char *letters1 = data[digits[0] - '2'];char *letters2 = data[digits[1] - '2'];char *letters3 = data[digits[2] - '2'];char *letters4 = data[digits[3] - '2'];for (int i = 0; letters1[i] != '\0'; i++) {for (int j = 0; letters2[j] != '\0'; j++) {for (int k = 0; letters3[k] != '\0'; k++) {for (int m = 0; letters4[m] != '\0'; m++) {result[*returnSize][0] = letters1[i];result[*returnSize][1] = letters2[j];result[*returnSize][2] = letters3[k];result[*returnSize][3] = letters4[m];result[*returnSize][4] = '\0';(*returnSize)++;}}}}}return result;
}

蛮力法做的话，需要有很清晰的逻辑思路，对嵌套循环有较深的了解和掌握。

（2）回溯法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** Note: The returned array must be malloced, assume caller calls free().*/
void backtrack(char* digits, int index, char** data, char* current, char** result, int* returnSize) {if (digits[index] == '\0') {result[*returnSize] = strdup(current);(*returnSize)++;return;}int digit = digits[index] - '2';char* letters = data[digit];for (int i = 0; letters[i] != '\0'; i++) {current[index] = letters[i];backtrack(digits, index + 1, data, current, result, returnSize);}
}char** letterCombinations(char* digits, int* returnSize) {char* data[8] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};*returnSize = 0;int len = strlen(digits);if (len == 0) {return NULL;}int maxCombinations = 1;for (int i = 0; i < len; i++) {if (digits[i] == '7' || digits[i] == '9') {maxCombinations *= 4;} else {maxCombinations *= 3;}}char** result = (char**)malloc(maxCombinations * sizeof(char*));char* current = (char*)malloc((len + 1) * sizeof(char));current[len] = '\0';backtrack(digits, 0, data, current, result, returnSize);free(current);return result;
}

采用回溯算法来生成所有可能的字母组合，这样可以避免嵌套循环过多的问题。

1. 回溯函数 backtrack：
   当处理完所有数字时，将当前组合复制到结果数组。
   对于每个数字，遍历其对应的字母，递归处理下一个数字。
2. 主函数 letterCombinations：
   若输入为空，返回 NULL。
   计算可能的组合数量，为结果数组分配内存。
   分配一个临时数组 current 用于存储当前组合。
   调用 backtrack 函数生成组合。
   释放临时数组的内存。