【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

作者:神秘网友 发布时间:2020-09-27 07:51:29

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码的字母组合(递归与回溯)

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

仰望星空的人,不应该被嘲笑

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

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

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

采用回溯做法,对于当前选项,我们可以重复选择,所以 for 循环那里从 0 开始,对于字母组合我们做一个 map映射即可。

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

参考 xiao_ben_zhu 大佬的图解

var letterCombinations = function (digits) {
  if(!digits.length) return [];
  // 直接映射
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let res = [];
  let dfs = (cur, start) => {
    if (start >= digits.length) {
      res.push(cur);
      return;
    }
    // 取当前可选的字母组合
    let str = map[digits[start]];
    for (let i = 0; i < str.length; i++) {
      dfs(cur + str[i], start + 1);
    }
  }
  dfs('', 0);
  return res;
};

解法2

这个是没用回溯之前写的一份代码,简单来说就是利用了层次遍历的特性,反正每次取字母都是可以重复的,直接遍历即可,然后进队列。

var letterCombinations = function(digits) {
  if(!digits.length) return []
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  let queue = []
  queue.push('')
  for(let i=0;i<digits.length;i++){
      let size = queue.length
      while(size--){
          let cur = queue.shift()
          let str = map[digits[i]]
          for(let j=0;j<str.length;j++){
              queue.push(cur+str[j])
          }
      }
  }
  return queue
};

文章产出不易,还望各位小伙伴们支持一波!

往期精选:

小狮子前端の笔记仓库

leetcode-javascript:LeetCode 力扣的 JavaScript 解题仓库,前端刷题路线(思维导图)

小伙伴们可以在Issues中提交自己的解题代码,?? 欢迎Contributing,可打卡刷题,Give a ?? if this project helped you!

访问超逸の博客,方便小伙伴阅读玩耍~

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码

学如逆水行舟,不进则退

【亡羊补牢】挑战数据结构与算法 第34期 LeetCode 17. 电话号码相关教程

  1. 【亡羊补牢】挑战数据结构与算法 第35期 LeetCode 22. 括号生成

    【亡羊补牢】挑战数据结构与算法 第35期 LeetCode 22. 括号生成(递归与回溯) 仰望星空的人,不应该被嘲笑 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3输出:[ ((())), (()()), (())(),

  2. 数据结构与算法——二叉树、堆、优先队列

    数据结构与算法——二叉树、堆、优先队列 七、树 7.1.1 树的定义 树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述现实生活中的很多事物,例如族谱、单位的组织架构、等等。 树是由n(n=1)个有限结点组成一个具有层次关系的集合。

  3. 【亡羊补牢】挑战数据结构与算法 第36期 LeetCode 236. 二叉树的

    【亡羊补牢】挑战数据结构与算法 第36期 LeetCode 236. 二叉树的最近公共祖先(二叉树) 仰望星空的人,不应该被嘲笑 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖

  4. [极客大挑战 2019]HardSQL(报错注入)

    [极客大挑战 2019]HardSQL(报错注入) 登入界面: 尝试关键字测试. 可以发现736的都被过滤了. 而且发现并没有具体的回显点. 于是尝试报错注入. 首先爆出表名. admin'or(updatexml(1,concat(0x7e,(select(table_name)from(information_schema.tables)where(table

  5. 概要数据结构(Sketch)

    概要数据结构(Sketch) 概念 概要数据结构(Sketch)包含 H 个长度为 P 的哈希表. 将网络流量数据建模为 (键,值) 的形式, 其中 “键” 为一个或多个数据包头中的字段, 例如源地址或源地址个目的地址的组合, “值”为存储的特征, 例如数据包的数量。

  6. HBase表的数据结构

    HBase表的数据结构 一.Table 传统数据库一个表的结构如下 姓名 年龄 性别 成绩 wuyifan 18 man 100 john 20 man 98 转换成HBase数据库的表结构就如下所示 info score Row_key info:name ,info:age ,info:sex score:name, score:score // 创建表和列族 // c

  7. 【亡羊补牢】挑战数据结构与算法 第42期 LeetCode 257. 二叉树的

    【亡羊补牢】挑战数据结构与算法 第42期 LeetCode 257. 二叉树的所有路径(二叉树) 仰望星空的人,不应该被嘲笑 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 输入: 1 / \2 3 \ 5输出: [1-2-5, 1-3]解释

  8. 数据结构详解系列:第五章 图

    数据结构详解系列:第五章 图 前言 本章主要详解了图的基本概念和存储,以及增删改查等操作实现,还有图的遍历和经典应用。其中包括使用邻接表存储图和邻接矩阵存储图、图的深度优先遍历和广度优先遍历,以及很重要的图的相关应用算法—最短路径求解(BFS算法