17. 电话号码的字母组合

难度：中等

题目

给定一个仅包含数字 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'] 的一个数字。

Reference

题解

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void dfs(char *digits, char **ret, int *subscript, char *current, int end, char **map)
{
    if (*digits == 0)
    {
        strcpy(ret[(*subscript)++], current);
        return;
    }
    int i = 0, target = *digits - '2';
    char *cur = map[target];
    while(*cur)
    {
        current[end] = *cur;
        dfs(digits + 1, ret, subscript, current, end + 1, map);
        cur++;
    }
}
char ** letterCombinations(char * digits, int* returnSize){
    *returnSize = 1;
    char *cur = digits, len = 0, *charMap[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    while(*cur)
    {
        *returnSize *= (*cur == '7' || *cur == '9') ? 4 : 3;
        cur++;
        len++;
    }
    if (len == 0)
    {
        *returnSize = 0;
        return NULL;
    }
    char **ret = (char **)malloc(sizeof(char *) * *returnSize),
         *current = (char *)memset(malloc(sizeof(char) * (len + 1)), 0, sizeof(char) * (len + 1));
    for (int i = 0; i < *returnSize; i++)
        ret[i] = (int *)memset(malloc(sizeof(char) * (len + 1)), 0, sizeof(char) * (len + 1));
    int subscript = 0;
    dfs(digits, ret, &subscript, current, 0, charMap);
    return ret;
}

评论