題目描述

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

思路整理

看到這個題，想法的算法就是枚舉，枚舉的實現也有也有多種方式?？梢圆捎醚h(huán)，也可以采用遞歸。
但是這道題首先要解決的是內存的問題，如何“一次性”申請一個合適大小的內存。因為C語言不具備動態(tài)申請內存的條件。如果采用C++ vector，多次創(chuàng)建string對象+容器操作，內存的復雜度會減小一點。本題可以考慮優(yōu)先構建號碼簿二維數組，再基于輸入的數字串計算出存儲結果的二維數組的大小。
其次要解決的問題，就是如果循環(huán)的問題，大體思路還是先循環(huán)輸入的字符串，對每一個數字所對應全部字母按樹形結構輪詢。
方案一：看到樹形結構，通常會優(yōu)先考慮采用遞歸的方式。
方案二：將該問題轉化為一個二維數組填值的問題，通過處理行和列的序列關系，分別對二維數組按行填值，這樣可以避免遞歸，直接用兩個for循環(huán)解決。
方案1是我想的，給出代碼，方案二是別人想的，我給出鏈接。

代碼show

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *letter_matrix[10];
int letter_length[10];

void gettable(char **letters,int *letters_index,char *digits,int offset,char *record,int record_offset)
{
    int i = 0;
    int loop = 0;
    if(digits[offset] == 0)
    {
        memcpy(letters[*letters_index],record,record_offset);
        *letters_index = *letters_index + 1;
        return;
    }
    int index = digits[offset] - '0';
    if (letter_length[index] > 0) {
            loop = letter_length[index];
    }
    for(i = 0;i < loop;i++)
    {
        record[record_offset] = letter_matrix[index][i];
        gettable(letters,letters_index,digits, offset + 1, record, record_offset + 1);
    }
}

/**
 ** Return an array of size *r eturnSize.
 ** Note: The returned array must be malloced, assume caller calls free().
 **/
static char** letterCombinations(char* digits, int* returnSize)
{
    letter_matrix[0] = "";
    letter_matrix[1] = " ";
    letter_matrix[2] = "abc";
    letter_matrix[3] = "def";
    letter_matrix[4] = "ghi";
    letter_matrix[5] = "jkl";
    letter_matrix[6] = "mno";
    letter_matrix[7] = "pqrs";
    letter_matrix[8] = "tuv";
    letter_matrix[9] = "wxyz";
    
    letter_length[0] = 0;
    letter_length[1] = 1;
    letter_length[2] = 3;
    letter_length[3] = 3;
    letter_length[4] = 3;
    letter_length[5] = 3;
    letter_length[6] = 3;
    letter_length[7] = 4;
    letter_length[8] = 3;
    letter_length[9] = 4;
    int i, j, k;
    int empty = 1;
    int count = 1;
    int digit_len = strlen(digits);
    for (i = 0; i < digit_len; i++) {
        int index = digits[i] - '0';
        if (letter_length[index] > 0) {
            empty = 0;
            count *= letter_length[index];
        }
    }

    if (empty) {
    *returnSize = 0;
        return NULL;
    }

    *returnSize = count;

    char **letters = malloc(sizeof(char *) * count);
    for (i = 0; i < count; i++) {
        letters[i] = malloc(digit_len + 1);
        memset(letters[i], 0, digit_len + 1);
    }
    char record[10] = {0};
    int letters_index=0;
    gettable(letters,&letters_index,digits,0,record,0);

    return letters;
}

int main(int argc, char **argv) {
    int i, size = 0;
    char test[10] = "249";
    char ** letters = letterCombinations(test, &size);
    for (i = 0; i < size; i++) {
        printf("%s\n", letters[i]);
        free(letters[i]);
    }
    free(letters);
    return 0;
}

方案二：
https://github.com/crazy-shawn-liu/leetcode/tree/master/051_n_queens

總結

1.確定初始二維數組的大小及布局。
2.確定遍歷得到數組值的方法。