c语言-c语言编程基础之leetcode题解第17题电话号码的字母组合.zip资源-CSDN文库

共3个文件

makefile：1个

cpp：1个

c：1个

需积分: 1 193 浏览量 2024-04-19 09:08:40 上传评论收藏 3KB ZIP 举报

在C语言编程中，LeetCode是一个非常受欢迎的在线平台，用于练习和提升编程技能，特别是算法和数据结构。第17题"电话号码的字母组合"是其中一道经典的题目，它涉及到了字符串处理、递归和回溯等编程概念。题目描述：给定一个仅包含数字2-9的字符串，每个数字对应一个电话键盘上的字母，如下所示： ``` 1 abc def ghi jkl mno pqrs tuv wxy z ``` 返回所有可能的字母组合，这些字母组合可以构成给定的数字字符串。结果可以按任何顺序返回。解决方案：解决这个问题的关键在于理解如何使用递归和回溯来生成所有可能的组合。以下是一个C语言实现的概述： 1. 定义一个字符数组，存储每个数字对应的字母。 2. 定义一个递归函数，接收当前处理到的数字索引和当前组合的字符串作为参数。 3. 当数字索引超过给定字符串长度时，说明已生成一个有效组合，将其添加到结果列表中。 4. 对于每个未处理的数字，将对应的字母集合作为新组合的首字符，调用递归函数处理下一个数字。 5. 在递归调用中，回溯时移除当前的首字符，尝试下一个字母。代码示例： ```c #include <stdio.h> #include <string.h> #include <stdlib.h> char* letters[] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxy", "z"}; void dfs(char** result, char* combination, int index, char* digits, int len) { if (index == len) { result[combination - digits] = strdup(combination); return; } int digit = digits[index] - '2' + 1; for (int i = 0; i < strlen(letters[digit]); i++) { combination[index] = letters[digit][i]; dfs(result, combination + index + 1, index + 1, digits, len); } } int* letterCombinations(char* digits, int* returnSize) { int len = strlen(digits); if (!len) return NULL; char** result = malloc(sizeof(char*) * 10000); // 假设最大组合数不超过10000 *returnSize = 0; char combination[len]; dfs(result, combination, 0, digits, len); return result; } int main() { int size; char** combinations = letterCombinations("23", &size); for (int i = 0; i < size; i++) { printf("%s\n", combinations[i]); free(combinations[i]); } free(combinations); return 0; } ``` 在这个示例中，`letterCombinations`函数是主要的接口，它首先检查输入字符串的长度，然后调用`dfs`进行深度优先搜索。`dfs`函数通过遍历每个数字的字母组合并递归地处理后续数字来生成所有可能的组合。在主函数中，我们打印出所有的组合，并确保正确释放内存。这个题目不仅考察了C语言的基本语法，还涉及到动态内存分配、字符串操作和高级的算法思想，是学习C语言编程和算法的好例子。通过理解和解决此类问题，程序员可以提高解决问题的能力，更好地应对实际开发中的挑战。

资源推荐

资源详情

资源评论

收起资源包目录

c语言_c语言编程基础之leetcode题解第17题电话号码的字母组合.zip （3个子文件）

c语言_c语言编程基础之leetcode题解第17题电话号码的字母组合

0017_letter_combinations_of_a_phone_number

letter_combinations.c 2KB

Makefile 59B

letter_combinations.cpp 914B

#include <stdio.h> #include <stdlib.h> #include <string.h> /** ** Return an array of size *returnSize. ** Note: The returned array must be malloced, assume caller calls free(). **/ static char** letterCombinations(char* digits, int* returnSize) { int i, j, k; int empty = 1; int count = 1; int digit_len = strlen(digits); char *letter_matrix[10] = {"", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", }; int letter_length[10] = {0, 1, 3, 3, 3, 3, 3, 4, 3, 4, }; for (i = 0; i < digit_len; i++) { int index = digits[i] - '0'; if (letter_length[index] > 0) { empty = 0; count *= letter_length[index]; } } if (empty) { *returnSize = 0; return NULL; } *returnSize = count; char **letters = malloc(sizeof(char *) * count); for (i = 0; i < count; i++) { letters[i] = malloc(digit_len + 1); memset(letters[i], 0, digit_len + 1); } int den = 1; for (i = digit_len - 1; i > 0; i--) { int index = digits[i] - '0'; if (letter_length[index] > 0) { den *= letter_length[index]; } } int col = 0; for (i = 0; i < digit_len; i++) { int index = digits[i] - '0'; if (letter_length[index] > 0) { if (i > 0) { int index2 = digits[i] - '0'; if (letter_length[index2] > 0) { den /= letter_length[index2]; } } for (j = 0; j < count; j++) { k = j / den % letter_length[index]; letters[j][col] = letter_matrix[index][k]; } col++; } } return letters; } int main(int argc, char **argv) { int i, size = 0; char ** letters = letterCombinations(argv[1], &size); for (i = 0; i < size; i++) { printf("%s\n", letters[i]); free(letters[i]); } free(letters); return 0; }

评论收藏

内容反馈