每周一道算法题(十三)

本周的算法题难度级别“Medium”,用了我三天工作之余的时间，总算过了，效率较低

题目:给你一串数字，在9宫格键盘上输入这串数，需要求所有可能得到的字符串

分析:题目其实就是手机的九宫格输入法，把按键的字母进行排列组合即可。明确了题目，下面就来实现本道题

• 确定行数和列数

我们可以发现，列数其实就是你输入数字的个数，行数就是数字代表字母个数的乘积

• 确字每行每列显示的字母

我发现的规律是：第一列的字母是你输入的第一个数字所代表的字母的循环，第二列是第二个数字对应字母的循环。。。最后一列循环的次数是最后一列字母的个数/最后一列字母的个数，倒数第二列的循环次数是（倒数第二列字母的个数 ＊ 倒数第一列字母的个数）/倒数第二列字母的个数，倒数第三列的循环次数是（倒数第三列字母的个数 ＊ 倒数第二列字母的个数 ＊ 倒数第一列字母的个数）/倒数第三列字母的个数。。。

通过以上的两个规则我们就能把这道题搞定了，由于这两个规则不好理解，我们先举个例子来理解下这两条规则，假设我们输入了2､3､4三个数字，则排列组合如下图：

通过第一条规则来确字行数和列数：2代表a/b/c三个字母,3代表d/e/f三个字母,4代表g/h/i三个字母,则行数为3＊3＊3=27行，输入了三个数字，所以列数为3

通过第二条规则来确定字母：我们先看最后一列，循环次数是3/3＝1,即只循环一次，则直接g-h-i的循环填序即可，看倒数第二列，循环次数是(3*3)/3=3,循环3次，则按照d-d-d,e-e-e,f-f-f循环填序即可，倒数第三列的循环次数是(3*3*3)/3=9,循环9次，即9个a，9个b，9个c的循环填序即可。思路上实现以后，我们就用代码来实现：

char** letterCombinations(char* digits, int* returnSize) {
    //列数就是输入数字的个数
    int column = (int)strlen(digits);
    //str用于存储输入数字所对应的字母
    char **str = malloc(column * sizeof(char *));
    //如果输入的个数为0
    if (column == 0) {
        *returnSize = 0;
        return str;
    }
    //通过计算每个数字所对应字母的个数的乘积来求出行数
    int row = 1;
    for (int i = 0;i < column; i++) {
        int num =  (int)(digits[i] - '0');
        if (num == 0) str[i] = " ";
        else if (num == 1) str[i] = "*";
        else if (num == 2) str[i] = "abc";
        else if (num == 3) str[i] = "def";
        else if (num == 4) str[i] = "ghi";
        else if (num == 5) str[i] = "jkl";
        else if (num == 6) str[i] = "mno";
        else if (num == 7) str[i] = "pqrs";
        else if (num == 8) str[i] = "tuv";
        else if (num == 9) str[i] = "wxyz";
        row *= (int)strlen(str[i]);
    }
    //result为结果
    char **result = malloc(row * sizeof(char *));
    for (int i = 0; i < row; i++) 
        result[i] = malloc(column+1);
    //为result填充字母
    for (int c = column - 1; c >= 0; c--) {
        //确定循环次数temp
        int temp = c,sum = 1;
        while (temp <= column - 1) {
            sum *= strlen(str[temp]);
            temp++;
        }
        temp = sum / strlen(str[c]);
        //按列填充字母
        int r = 0;
        while (r < row) {
            result[r][c] = str[c][r/temp%strlen(str[c])];
            r++;
        }
        //填充结束符'\0'
        if (c == 0) {
            int r = 0;
            while (r < row) {
                result[r][column] = '\0';
                r++;
            }
        }
    }
    //返回结果
    *returnSize = row;
    return result;
}

这道题用了一天多的空闲时间就总结出了规律，思路一直没错（应该不是最优思路），但代码实现却花了我近两天的时间，不得不叹息想法和做法之间还是有一些距离，代码实现中主要的问题是内存问题，着实的被strlen这个函数坑了好久，又被'\0'这个坑坑了半天，也使得我对指针、c语言内存机制等方面又有了新的认识，看来光有想法还不够，程序猿就要多敲代码，将想法落地才能更好的成长，做出来了也是有成就感的。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!