leadcode的Hot100系列--17. 電話號碼的字母組合--回溯的另一種應用

提交leetcode的時候遇到了問題，一直說訪問越界，但仔仔細細檢查n多遍，就是檢查不出來。
因為我用到了count全局變數，自加一來表明當前數組訪問的位置，
後來突然想到，是不是在leetcode在運行測試用例的時候，是連續測試的，用的同一個上下文，這樣的話，就沒有對這個全局變數清零……
果然，清零之後就可以了……已經3:47了，這裡先上代碼，明天再詳細說吧……

今天更新一下這道題的思路。
可以先參考一下之前的兩篇文章，循序漸進，好理解一些：
leadcode的Hot100系列--78. 子集--位運算
leadcode的Hot100系列--78. 子集--回溯

在 子集--回溯 的文章裡面，介紹了一下數字的排列組合，用01來表示對應的數字是否存在。
如果我們還是按照這個思路，但是換一個想法呢？
0、1是不是本身就可以代表著字元串？
對應排列出來的000\001\010 ... 是不是就是相當於：
我需要一個數字組合，組合需要三位數，每一位的數字要麼是0，要麼是1。
這麼一想，是不是就與題目一致了：
我需要一個字母組合，組合的位數就是輸入的字元串長度，每一位的字母是對應的幾個字母中的某一個。
對，就是這麼想的，比如，輸入“89”，就說明，字母組合的位數是兩位，第一位字母是'tuv'裡面的一個，第二位字母是'wxyz'裡面的一個。
這裡再看下之前上一篇中回溯的代碼：

void backtrack (int t)
{
    if (t == level)
        show();
    else  
        for (int i=0;i<=1;i++)
        {
            y[t]=i; 
            backtrack(t+1);
        }
}

重點來了！！！！

• 第三行的level表示層數，也就是遍歷的深度，也就是組合所需要的位數，當需要兩位字母的時候，就只要兩層。
• 第六行的for迴圈，表示了每一層的選項，之前因為只需要表示存在和不存在，所以只需要用0和1就夠了，但在這裡，是由數字對應的字元串的某一個，例如如果數字是8，則對應的選項就是't'和'u'和'v'。

所以，當輸入為“89”的時候，就可以生成這樣一種樹：

控制了樹的層數和樹的分支（分支就是可選項）之後，就可以完成所有組合。

char table[][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
char level = 0;
char *p[8];   // 指向數字對應的字元串，例如，當輸入數字為"89"時,p[0]為"tuv",p[1]為"wxyz"。
char len[8];  // 對應上面p存儲的字元串的長度，例如，當輸入數字為"89"是，len[0]=3,len[1]=4。
char **out; //二維數組，是最終輸出
int count = 0; // 用來記錄當前已經生成了幾個組合，對應著out數組的行坐標
char y[8] = {0}; // 記錄每一次的組合結果

void backtrack(int level_now)
{
    if (level_now == level)
    {
        memcpy(out[count], y, level);  // 把這次組合結果拷貝到out數組中。這裡為什麼需要用一個y數組來記錄組合結果，然後拷貝到out中呢？大家可以自己想一想
        count ++;   // 完成一個字元串
        return;
    }
    for (int i=0; i<len[level_now]; i++)
    {
        y[level_now] = p[level_now][i];
        backtrack(level_now+1);
    }
    return;
}

char ** letterCombinations(char * digits, int* returnSize){
    level = strlen(digits);  // 遍歷的層數
    *returnSize = 0;
    if (0 == level) return NULL;
    
    *returnSize = 1;
    
    for(int i=0; i<level; i++)
    {
        p[i] = table[digits[i]-'0'];  // 對p數組進行賦值
        len[i] = strlen(p[i]);
        if (len[i] == 0)
        {
            *returnSize = 0;
            return NULL;
        }
        *returnSize *= len[i];    // 計算總共有多少個組合
    }
    out = (char **)calloc(*returnSize, sizeof(char *));  // 先分配行指針
    if (NULL == out) return NULL;
    for (int i=0; i<*returnSize; i++)
    {
        out[i] = (char *)calloc(1, sizeof(char) * (level+1));  // 再分配每個行指針的內容，因為字元串後面需要一個結束符'\0'，所以這裡需要level+1
        if (NULL == out[i]) return NULL;
    }
    backtrack(0);
    count = 0;   // 這裡很重要！很重要！！很重要！！！
    return out;
}