电话号码的字母组合

2024/10/25 10:29:36 来源：https://blog.csdn.net/weixin_48941116/article/details/143093511 浏览: 次关键词：电话号码的字母组合

力扣第十七题：电话号码的字母组合

问题描述

给定一个仅包含数字的字符串 digits，每个数字对应着字母组合，要求返回所有可能的字母组合。数字到字母的映射与电话键盘上的映射一致。

解题思路

映射建立：首先需要建立数字与字母之间的映射关系，可以使用字符数组或者函数来返回对应的字母字符串。
回溯法：通过递归和回溯的方法生成所有可能的组合：
- 当达到字符串的末尾时，将当前组合加入结果中。
- 否则，获取当前数字对应的字母集合，逐个添加到组合中，并递归调用函数继续处理下一个数字。
动态内存管理：使用动态内存分配来存储结果和当前的组合字符串，以适应不同大小的输入。

代码实现

以下是实现上述思路的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>char* digitToChar(char digit) {switch (digit) {case '2': return "abc";case '3': return "def";case '4': return "ghi";case '5': return "jkl";case '6': return "mno";case '7': return "pqrs";case '8': return "tuv";case '9': return "wxyz";default: return "";}
}void backtrack(char*** result, char* combination, const char* digits, int index, int* returnSize, int* capacity) {if (index == strlen(digits)) {if (*returnSize >= *capacity) {*capacity *= 2; // 扩展容量*result = realloc(*result, sizeof(char*) * (*capacity)); // 修改传入的指针if (*result == NULL) {exit(EXIT_FAILURE); // 处理 realloc 失败}}(*result)[*returnSize] = strdup(combination); // 复制组合到结果中(*returnSize)++;return;}char* letters = digitToChar(digits[index]);for (int i = 0; letters[i] != '\0'; i++) {combination[index] = letters[i]; // 添加当前字母backtrack(result, combination, digits, index + 1, returnSize, capacity); // 递归}combination[index] = '\0'; // 恢复组合状态
}char** letterCombinations(char* digits, int* returnSize) {if (strlen(digits) == 0) {*returnSize = 0;return NULL;}int capacity = 100; // 初始化容量char** result = malloc(sizeof(char*) * capacity);char* combination = malloc(sizeof(char) * (strlen(digits) + 1));combination[strlen(digits)] = '\0'; // 终止符*returnSize = 0;backtrack(&result, combination, digits, 0, returnSize, &capacity);free(combination); // 释放组合内存return result;
}int main() {char digits[] = "23";int returnSize;char** combinations = letterCombinations(digits, &returnSize);printf("Combinations:\n");for (int i = 0; i < returnSize; i++) {printf("%s\n", combinations[i]);free(combinations[i]); // 释放内存}free(combinations);return 0;
}

代码详解

数字到字母的映射：函数 digitToChar 将输入的数字转换为对应的字母字符串。
回溯过程：
- 在 backtrack 函数中，检查当前索引是否已达到字符串末尾。如果是，则将当前组合复制到结果数组中。
- 否则，从数字中获取对应的字母集合，逐个遍历并递归调用，直到生成所有组合。
动态内存管理：
- 初始化容量为 100，并在需要时使用 realloc 扩展数组的大小，确保能够容纳所有可能的组合。
复杂度分析：
- 时间复杂度：O(4^N)，每个数字最多对应 4 个字母，因此组合的总数是指数级别的。
- 空间复杂度：O(N)，存储组合所需的内存。