[路飞]_17. 电话号码的字母组合

「这是我参与2022首次更文挑战的第28天，活动详情查看：2022首次更文挑战」

17. 电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例1

输入： digits = "23"
输出： ["ad","ae","af","bd","be","bf","cd","ce","cf"]

实例2

输入： digits = "2"
输出： ["a","b","c"]

题解

全排列思想： 递归 + 回溯

首先肯定是要先将参数转换为字符串；构建一个哈希表将数字与字母关系一一对应： map={2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz,}map = \{ 2: abc, 3: def, 4: ghi, 5: jkl, 6: mno, 7: pqrs, 8: tuv, 9: wxyz, \}map={2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz,}

得到数字与字母关系一一对应

举个例子：digits="23" digits = "23"digits="23"，对应的字符串可以表示为 list=[abc,def]list = [abc,def]list=[abc,def]

返回所有它能表示的字母组合,是不是就是 list 数组中所有字符串全排列组合呀？

按照全排列思想，递归 + 回溯 一定可以解决问题的

如何递归？

const len = list.length
// 开始递归
dfs(0, []);

// idx ： 表示list中下标
function dfs(idx, path) {

    // 最终组成的字符串长度一定等于 list，并且这也是递归的终止条件
  if (path.length === len) {
    return;
  }
  for (let i = 0; i < (3||4); i++) {
      // (3||4)：或者是3或者是4，因为数字7表示字母pqrs，有4位，所以i可能小于3或者小于4，是动态的；
      // 这里就体现 idx 的价值了，idx表示list中下标，i < (3||4); 可以修改为 i  < list[idx].length
  }
}

如何回溯？

for (let i = 0; i < list[idx].length; i++) {
      const s = list[idx][i];
      //符合条件字母的添加到路径上保存
      path.push(s);
      // 递归下一步
      dfs(idx + 1, path);
      // 回溯，递归结束后删除
      path.pop();
      
  }

路径保存字母为什么使用数组？因为回溯的时候操作数组比操作字符串方便

根据上述思路编辑代码如下：

完整代码

const map = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz',
};
var letterCombinations = function (digits) {
  const len = digits.length;
  if (len === 0) return [];
  const list = [];
  for (let i = 0; i < len; i++) {
    const k = digits[i];
    list.push(map[k]);
  }
  const result = [];
  dfs(0, []);
  return result;
  function dfs(idx, path) {
    if (path.length === len) {
      const t = path.join('');
      result.push(t);
      return;
    }

    for (let i = 0; i < list[idx].length; i++) {
      const s = list[idx][i];
      path.push(s);
      dfs(idx + 1, path);
      path.pop();
    }
  }
};