这道题目的本质是笛卡尔积问题，可以通过DFS求解，分别采用C/Java语言实现
#include <stdio.h>
#include <stdlib.h>
char *phoneMap[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
static char **combinations; // 记录最终结果
static int combinations_size;
static char *combination; // 记录每次回溯的字符串
static int combination_size;
void backtrack(char *digits, int size, int index) {
if (index == size) {
char *tmp = (char *) malloc(sizeof(char) * (combination_size + 1));
memcpy(tmp, combination, sizeof(char) * (combination_size + 1));
combinations[combinations_size++] = tmp;
return;
}
char *letters = phoneMap[digits[index] - '0'];
int len = strlen(letters);
for (int i = 0; i < len; i++) {
combination[combination_size++] = letters[i];
combination[combination_size] = '\0'; // 记录结束标识
backtrack(digits, size, index + 1);
combination[--combination_size] = '\0'; // 状态复原
}
}
char **letterCombinations(char *digits, int *returnSize) {
combinations_size = combination_size = 0; // 在入口函数初始化0，不然leetcode编译报错
int digits_size = strlen(digits);
if (digits_size == 0) {
*returnSize = 0;
return combinations;
}
int num = 1;
for (int i = 0; i < digits_size; i++) num *= 4;
combinations = (char **) malloc(sizeof(char *) * num);
combination = (char *) malloc(sizeof(char *) * digits_size);
backtrack(digits, digits_size, 0);
*returnSize = combinations_size;
return combinations;
}
int main() {
char *str = "23";
int ret = 0;
char **res = letterCombinations(str, &ret);
for (int i = 0; i < ret; i++) {
printf("%s\n", *(res + i));
}
}