LeetCode-中等-17-电话号码的字母组合(C)

这算是我第一次能正常分配二级指针内存的题了。

题目

给定一个仅包含数字 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首先要计算返回数组的大小，可以知道，只有7、9两键有四个字符，其他都是三个，即不同键只有两个返回结果，因此用三元运算符表示当前键的大小，将每个键累乘即可得到returnSize。

之后是空间分配，二级指针空间分配看这篇：C语言二级字符串指针的使用(函数传参/长度获取/空间分配)

分配完每个空间之后顺便将字符的最后一个值设置为'\0'，就不用后面拼接的时候找麻烦了。

在拼接字符串时，想要以尽可能少的时间跑出结果，就要观察字符串的构成规律。
假设tempSize=returnSize，当我们对输入"234" 赋值时，此时returnSize = 3*3*3=27，
对letterResult[0~26][0]赋值时，可以看出，每9个为一组，赋值一样，循环了1遍，即a a a a a a a a a b b b b b b b b b c c c c c c c c c。
对letterResult[0~26][1]赋值时，可以看出，每3个为一组，赋值一样，循环了3遍，即d d d e e e f f f d d d e e e f f f d d d e e e f f f。
对letterResult[0~26][2]赋值时，可以看出，每1个为一组，赋值一样，循环了9遍，即g h i g h i g h i g h i g h i g h i g h i g h i g h i。
容易看出，从第一个字符到最后一个字符赋值的过程中，每右移一个字符，每组的数量都变为原来的1/3，循环次数变为原来的3倍。
分析可知，倍数是与当前键的字符个数有关的，为7、9时是1/4、4倍。
如果要用公式表示，就得从取余与整除入手。
耗费脑细胞可知，第pos个字符串的第i个字符，是键中的第pos % tempSize / (tempSize/keySize)个字符，每次右移字符时，tempSize/=keySize;

代码中各变量释义：
digits[][]; //传参，键字符串
int tempSize = returnSize; //临时长度
char **letterResult; //返回数组
int pos; //第二层循环，表示第pos个字符串
int i; //第一层循环，表示第pos个字符串中的第i个字符
int keySize = (digits[i] == '7' || digits[i] == '9') ? 4 : 3; //当前键的大小（下面代码使用中直接用了三元运算符，没有用变量keySize表示）

代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ** letterCombinations(char * digits, int* returnSize) {
    char letterDictionary[8][5] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    char **letterResult;
    int i, pos, tempSize;
    //特殊情况处理
    if(strlen(digits)==0){
        *returnSize=0;
        return NULL;
    }
    //空间大小获取与初始化
    *returnSize = 1;
    for (i = 0; digits[i] != '\0'; i++) {
        *returnSize *= (digits[i] == '7' || digits[i] == '9') ? 4 : 3;
    }
    letterResult = (char**)malloc((*returnSize)*sizeof(char*));
    for (i = 0; i < (*returnSize); i++) {
        *(letterResult + i) = (char*)malloc((strlen(digits) + 1)*sizeof(char));
        letterResult[i][strlen(digits)] = '\0';
    }
    //字符串合成
    tempSize = (*returnSize);
    for (i = 0; digits[i] != '\0'; i++) {
        for (pos = 0; pos < *returnSize; pos++) {
            letterResult[pos][i] = letterDictionary[digits[i] - '2'][(pos) % tempSize / (tempSize / ((digits[i] == '7' || digits[i] == '9') ? 4 : 3))];
        }
        tempSize /= ((digits[i] == '7' || digits[i] == '9') ? 4 : 3);
    }
    return letterResult;
}