Leetcode17电话号码的字母组合

17电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

逐个字符转化
执行用时：0 ms
内存消耗：5.6 MB

void char2letter(char digit, char *first, char *second, char *third, char *fourth)
{
    if ('2' <= digit && digit <= '6')
    {
        *first = 'a' + (digit - '2') * 3;
        *second = 'b' + (digit - '2') * 3;
        *third = 'c' + (digit - '2') * 3;
        *fourth = '\0';
    }
    else if (digit == '7')
    {
        *first = 'p';
        *second = 'q';
        *third = 'r';
        *fourth = 's';
    }
    else if (digit == '8')
    {
        *first = 't';
        *second = 'u';
        *third = 'v';
        *fourth = '\0';
    }
    else if (digit == '9')
    {
        *first = 'w';
        *second = 'x';
        *third = 'y';
        *fourth = 'z';
    }
    else
    {
        *first = '\0';
        *second = '\0';
        *third = '\0';
        *fourth = '\0';
    }
}

char **letterCombinations(char *digits, int *returnSize)
{
    if (*digits == '\0')
    {
        *returnSize = 0;
        return calloc(sizeof(char), sizeof(char));
    }
    int len_max = strlen(digits), len = 0;
    char **result;
    char first, second, third, fourth;
    int size, i;
    *returnSize = 1;
    for (i = 0; i < len_max; i++)
    {
        if (digits[i] == '7' || digits[i] == '9')
            *returnSize *= 4;
        else
            *returnSize *= 3;
    }
    result = calloc(*returnSize * sizeof(char *), sizeof(char *));
    for (size = 0; size < *returnSize; size++)
        result[size] = calloc((len_max + 1) * sizeof(char), sizeof(char));
    size = 1;
    while (*digits != '\0')
    {
        char2letter(*digits, &first, &second, &third, &fourth);
        if (fourth == '\0')
        {
            for (i = 0; i < size; i++)
            {
                memcpy(result[i + size], result[i], (len_max + 1) * sizeof(char));
                memcpy(result[i + size * 2], result[i], (len_max + 1) * sizeof(char));
            }
            for (i = 0; i < size; i++)
                result[i][len] = first;
            for (i = size; i < size * 2; i++)
                result[i][len] = second;
            for (i = size * 2; i < size * 3; i++)
                result[i][len] = third;
            size *= 3;
            len += 1;
        }
        else
        {
            for (i = 0; i < size; i++)
            {
                memcpy(result[i + size], result[i], (len_max + 1) * sizeof(char));
                memcpy(result[i + size * 2], result[i], (len_max + 1) * sizeof(char));
                memcpy(result[i + size * 3], result[i], (len_max + 1) * sizeof(char));
            }
            for (i = 0; i < size; i++)
                result[i][len] = first;
            for (i = size; i < size * 2; i++)
                result[i][len] = second;
            for (i = size * 2; i < size * 3; i++)
                result[i][len] = third;
            for (i = size * 3; i < size * 4; i++)
                result[i][len] = fourth;
            size *= 4;
            len += 1;
        }
        digits++;
    }
    *returnSize = size;
    return result;
}