【回溯】电话号码的字母组合

解题思路：回溯算法

变量：path字符串记录当前路径，ans字符串记录所有答案

递归结束条件：path字符串长度等于原字符串长度

1.每次遍历使用for循环遍历三次，每次将当前元素的对应的一种字母返回，压入path

2.当path长度等于digits长度时，返回

char* path;
int pathTop;
char** ans;
int ansTop;
char get_corresponding_char(char digit, int index) {
    switch(digit) {
        case '2':
            if(index == 0)
                return 'a';
            else if(index == 1)
                return 'b';
            else if(index == 2)
                return 'c';
            break;
        case '3':
            if(index == 0)
                return 'd';
            else if(index == 1)
                return 'e';
            else if(index == 2)
                return 'f';
            break;
        case '4':
            if(index == 0)
                return 'g';
            else if(index == 1)
                return 'h';
            else if(index == 2)
                return 'i';
            break;
        case '5':
            if(index == 0)
                return 'j';
            else if(index == 1)
                return 'k';
            else if(index == 2)
                return 'l';
            break;
        case '6':
            if(index == 0)
                return 'm';
            else if(index == 1)
                return 'n';
            else if(index == 2)
                return 'o';
            break;
        case '7':
            if(index == 0)
                return 'p';
            else if(index == 1)
                return 'q';
            else if(index == 2)
                return 'r';
            else if(index == 3)
                return 's';
            break;
        case '8':
            if(index == 0)
                return 't';
            else if(index == 1)
                return 'u';
            else if(index == 2)
                return 'v';
            break;
        case '9':
            if(index == 0)
                return 'w';
            else if(index == 1)
                return 'x';
            else if(index == 2)
                return 'y';
            else if(index == 3)
                return 'z';
            break;
    }
    //应该不会走到这里
    return 'a';
}

int my_strlen(char* digits) {
    char* pt = digits;
    int length = 0;
    while(*pt) {
        length++;
        pt++;
    }
    return length;
}

int corLength(char digit) {
    if(digit == '7' || digit == '9')
        return 4;
    return 3;
}

void backTracking(char* digits, int length) {
    if(pathTop == length) {
        char* tempPath = (char*)malloc(sizeof(char) * length + 1);
        int j;
        for(j = 0; j < length; j++) 
            tempPath[j] = path[j];
        tempPath[length] = 0;
        ans[ansTop++] = tempPath;
        return;
    }
    int i;
    for(i = 0; i < corLength(*digits); i++) {
        path[pathTop++] = get_corresponding_char(*digits, i);
        backTracking(digits+1,length);
        pathTop--;
    }
}

char ** letterCombinations(char * digits, int* returnSize){
    int digitsLength = my_strlen(digits);
    path = (char*)malloc(sizeof(char) * digitsLength + 1);
    ans = (char**)malloc(sizeof(char*) * 1000);
    pathTop = 0;
    ansTop = 0;
    if(digitsLength == 0) {
        *returnSize = 0;
        return ans;
    }
    backTracking(digits, digitsLength);
    *returnSize = ansTop;
    return ans;
}

算法改进：

char* path;
int pathTop;
char** result;
int resultTop;
char* letterMap[10] = {"", //0
        "", //1
        "abc", //2
        "def", //3
        "ghi", //4
        "jkl", //5
        "mno", //6
        "pqrs", //7
        "tuv", //8
        "wxyz", //9
};
void backTracking(char* digits, int index) {
    //若当前下标等于digits数组长度
    if(index == strlen(digits)) {
        //复制digits数组，因为最后要多存储一个0，所以数组长度要+1
        char* tempString = (char*)malloc(sizeof(char) * strlen(digits) + 1);
        int j;
        for(j = 0; j < strlen(digits); j++) {
            tempString[j] = path[j];
        }
        //char数组最后要以0结尾
        tempString[strlen(digits)] = 0;
        result[resultTop++] = tempString;
        return ;
    }
    //将字符数字转换为真的数字
    int digit = digits[index] - '0';
    //找到letterMap中对应的字符串
    char* letters = letterMap[digit];
    int i;
    for(i = 0; i < strlen(letters); i++) {
        path[pathTop++] = letters[i];
        //递归，处理下一层数字
        backTracking(digits, index+1);
        pathTop--;
    }
}

char ** letterCombinations(char * digits, int* returnSize){
    //初始化path和result
    path = (char*)malloc(sizeof(char) * strlen(digits));
    result = (char**)malloc(sizeof(char*) * 300);

    *returnSize = 0;
    //若digits数组中元素个数为0，返回空集
    if(strlen(digits) == 0) 
        return result;
    pathTop = resultTop = 0;
    backTracking(digits, 0);
    *returnSize = resultTop;

    return result;
}