一、C语言实现
/** * Note: The returned array must be malloced, assume caller calls free(). */char *letterNumber[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};int len;char *digitsBak;char **res;int resSize;char *resItem;int resItemSize;void backTrack(int index){ if (index == len) { // 给tmp调配空间 char *tmp = malloc(sizeof(char) * (resItemSize + 1)); memcpy(tmp, resItem, sizeof(char) * (resItemSize + 1)); res[resSize++] = tmp; } else { // 取输出的字符串中的数字字符，将其转换为数字，作为下标获取数字对应的字符串 int digitIndex = digitsBak[index] - '0'; char *letters = letterNumber[digitIndex]; int lettersLen = strlen(letters); for (int i = 0; i < lettersLen; i++) { resItem[resItemSize++] = letters[i]; resItem[resItemSize] = 0; backTrack(index + 1); resItem[--resItemSize] = 0; } }}char **letterCombinations(char *digits, int *returnSize){ len = strlen(digits); resSize = 0; resItemSize = 0; if (len == 0) { *returnSize = 0; return NULL; } int count = 1; digitsBak = digits; for (int i = 0; i < len; i++) { count *= 4; } res = (char **)malloc(count * sizeof(char *)); resItem = (char *)malloc(sizeof(char) * (len + 1)); backTrack(0); *returnSize = resSize; return res;}二、JS实现
/** * @param {string} digits * @return {string[]} */const letterCombinations = function (digits) { const len = typeof digits === 'string' && digits.length if (len === 0) { return [] } // 申明一个对象，存储数字与字符串的对应关系 const letterNumber = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' } const res = [] const arr = [] // 将与输出数字对应的字符串存储到一个数组中备用 for (const digit of digits) { arr.push(letterNumber[digit]) } const backTrack = function (str, index) { // 递归进口，当深度与输出的数字个数统一时，将获取的str存储，并不再递归调用 // 此时程序进入下一次循环 if (index === len) { res.push(str) } else { for (const letter of arr[index]) { // 此处必须用一个新的变量传递到递归调用的函数中 // 不能间接批改str的值，当上面的递归完结，回溯到此循环时， // str须要的是本层循环开始时的初始值，因而不能间接str += letter const tmp = str + letter backTrack(tmp, index + 1) } } } backTrack('', 0) return res}工夫复杂度：O(3^m4^n)，其中m是输出中对应3个字母的数字个数（包含数字 22、33、44、55、66、88），n是输出中对应4个字母的数字个数（包含数字 77、99），m+n是输出数字的总个数。当输出蕴含m个对应3个字母的数字和n个对应4个字母的数字时，不同的字母组合一共有 3^m 4^n种，须要遍历每一种字母组合。
空间复杂度：O(m+n)，其中m是输出中对应3个字母的数字个数，n是输出中对应4个字母的数字个数，m+n是输出数字的总个数。除了返回值以外，空间复杂度次要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输出无关，能够看成常数，递归调用层数最大为 m+n。