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;
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注