关于javascript:17-电话号码的字母组合LeetCodeC语言和JS

一、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。