likes
comments
collection
share

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

作者站长头像
站长
· 阅读数 44

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

17. 电话号码的字母组合

题目

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

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

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

示例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();
    }
  }
};
转载自:https://juejin.cn/post/7064554365721247780
评论
请登录