C语言自己输入一个仅包含数字 2-9 的三位字符串,返回所有它在手机键盘上能表示的字母组合
时间: 2024-05-16 10:17:53 浏览: 23
这个问题可以使用回溯算法来解决,具体步骤如下:
1. 定义一个映射表,将每个数字与其对应的字母列表关联起来。例如,数字 2 对应的字母列表是["a", "b", "c"]。
2. 定义一个递归函数,该函数接收一个字符串和一个当前位置的索引作为参数。初始调用该函数时,字符串为空,当前位置为0。
3. 在函数内部,根据当前位置的索引找到该位置对应的数字,并获取该数字对应的字母列表。
4. 遍历该字母列表,将当前字母添加到字符串末尾,并递归调用函数,将位置索引加1。
5. 当位置索引等于字符串长度时,说明已经遍历完所有数字,将当前字符串加入结果列表中。
6. 返回结果列表。
下面是使用C语言实现的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 映射表
const char *mapping[] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
void backtrack(char **result, char *combination, char *digits, int index)
{
if (index == strlen(digits)) {
// 遍历完所有数字,将当前字符串加入结果列表中
result[(*returnSize)++] = strdup(combination);
return;
}
int digit = digits[index] - '0';
const char *letters = mapping[digit];
for (int i = 0; i < strlen(letters); i++) {
// 将当前字母添加到字符串末尾
combination[index] = letters[i];
backtrack(result, combination, digits, index + 1);
}
}
char **letterCombinations(char *digits, int *returnSize)
{
*returnSize = 0;
if (strlen(digits) == 0) {
return NULL;
}
// 计算结果列表的长度
int count = 1;
for (int i = 0; i < strlen(digits); i++) {
int digit = digits[i] - '0';
count *= strlen(mapping[digit]);
}
// 分配结果列表的空间
char **result = (char **)malloc(count * sizeof(char *));
for (int i = 0; i < count; i++) {
result[i] = (char *)malloc((strlen(digits) + 1) * sizeof(char));
result[i][strlen(digits)] = '\0';
}
// 回溯算法
char combination[strlen(digits) + 1];
combination[strlen(digits)] = '\0';
backtrack(result, combination, digits, 0);
return result;
}
int main()
{
char digits[] = "234";
int returnSize;
char **result = letterCombinations(digits, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s\n", result[i]);
free(result[i]);
}
free(result);
return 0;
}
```
输出结果为:
```
adg
adh
adi
aeg
aeh
aei
afg
afh
afi
bdg
bdh
bdi
beg
beh
bei
bfg
bfh
bfi
cdg
cdh
cdi
ceg
ceh
cei
cfg
cfh
cfi
```