题目:
给定一个仅包含数字 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;
}
采用回溯算法来生成所有可能的字母组合,这样可以避免嵌套循环过多的问题。
- 回溯函数 backtrack:
当处理完所有数字时,将当前组合复制到结果数组。
对于每个数字,遍历其对应的字母,递归处理下一个数字。 - 主函数 letterCombinations:
若输入为空,返回 NULL。
计算可能的组合数量,为结果数组分配内存。
分配一个临时数组 current 用于存储当前组合。
调用 backtrack 函数生成组合。
释放临时数组的内存。