题目

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

分析

手机上的拼音输入法，每个数字键代表多个字母。
根据输入的数字串，返回可能的字符串
下面的C代码已通过。
先初始化二维字符数组，然后如果出现0或者1，或者数字串为空，就直接返回空。然后再依次递归判断接下来的字符，根据不同的数字表示不同的字符，之后在找到最后一个字符的时候，将该字符串存入结果字符串数组中。

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

void combination(char *digits,int digitsLength,char ** ans,int *returnSize,char *temp,int tempLength)
{
    if(digits[digitsLength]==NULL)
    {
        char * ansTemp=(char *)malloc(sizeof(char)*1000);
        int i=0;
        for(i=0;i<tempLength;i++)
        ansTemp[i]=temp[i];
        ansTemp[i]='\0';
        ans[*returnSize]=ansTemp;
        *returnSize=*returnSize+1;
        //printf("%s %d\n",ansTemp,*returnSize);
    }
    else if(digits[digitsLength]=='2')
    {
        digitsLength++;
        temp[tempLength]='a';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='b';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='c';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='3')
    {
        digitsLength++;
        temp[tempLength]='d';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='e';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='f';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='4')
    {
        digitsLength++;
        temp[tempLength]='g';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='h';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='i';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='5')
    {
        digitsLength++;
        temp[tempLength]='j';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='k';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='l';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='6')
    {
        digitsLength++;
        temp[tempLength]='m';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='n';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='o';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='7')
    {
        digitsLength++;
        temp[tempLength]='p';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='q';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='r';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='s';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='8')
    {
        digitsLength++;
        temp[tempLength]='t';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='u';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='v';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
    else if(digits[digitsLength]=='9')
    {
        digitsLength++;
        temp[tempLength]='w';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='x';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='y';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        temp[tempLength]='z';
        combination(digits,digitsLength,ans,returnSize,temp,tempLength+1);
        tempLength++;
    }
}
char** letterCombinations(char* digits, int* returnSize) {
    int i=0;
    char **ans=(char **)malloc(sizeof(char *)*1000000);
    *returnSize=0;
    char *temp=(char *)malloc(sizeof(char)*1000);
    if(digits[i]=='\0')
    return NULL;
    while(digits[i]!='\0')
    {
        if(digits[i]=='0'||digits[i]=='1')
            return NULL;
        i++;
    }
    combination(digits,0,ans,returnSize,temp,0);
    return ans;
}

当然还有更简单的方法，先处理前两个数字尽可能多的字符串，之后依次根据后面的数字再组成更多的字符串，可能需要重复赋值，但是相对的内存空间消耗较少。而我的方法多次递归，消耗大量栈空间。