[Java·算法·中等]LeetCode17. 电话号码的字母组合
每天一题,防止痴呆
- 题目
- 示例
- 分析思路1
- 题解1
- 分析思路2
- 题解2
题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入:digits = ""
输出:[]
输入:digits = "2"
输出:["a","b","c"]
分析思路1
可以使用递归的方式来实现。
使用了一个数组来保存数字与字母的对应关系。在递归过程中,我们不断地向已有的组合中添加新的字母,直到所有数字都被处理完毕。
题解1
class Solution {// 定义数组存储每个数字对应的字母,下标0和1均为空private final String [] arr = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>();if(digits == null || digits.length() == 0){return res;}backtrack(digits, 0, "", res);return res;}private void backtrack(String digits, int index, String combination, List<String> res){if(index == digits.length()){res.add(combination);return;}// 利用char变量使用 ASCII进行算术运算这一特征,可以得到一种间接计算获取数值的方法// '0'-'9' ASCII 为 48-57,且顺序一致,因而char数字之间的差值等于数字之间的差值String letters = arr[digits.charAt(index) - '0'];for(int i = 0; i < letters.length(); i++){backtrack(digits, index + 1, combination + letters.charAt(i), res);}}
}
执行结果

分析思路2
使用回溯算法进行求解。
首先,定义一个哈希表,将每个数字对应的字母存入其中,以便后续查找。
然后,定义一个结果列表 res,用于存储所有的字母组合。
接着,调用回溯函数 backtrack,该函数的参数为当前要处理的电话号码字符串 digits、当前要处理的字符索引 index、当前已经组合好的字母字符串 combination 和结果列表 res。
在回溯函数中,首先判断当前要处理的字符索引是否等于电话号码字符串的长度,如果是,说明已经处理完了所有的字符,此时将当前已经组合好的字母字符串 combination 添加到结果列表 res 中,并返回。
如果当前要处理的字符索引小于电话号码字符串的长度,说明还有字符需要处理。首先从哈希表中获取当前数字对应的字母列表 letters,然后依次枚举其中的每个字母,并将其添加到当前已经组合好的字母字符串 combination 的末尾,然后递归调用回溯函数 backtrack,处理下一个字符。
在递归返回后,需要将当前已经组合好的字母字符串 combination 的末尾字符删除,以便后续枚举其他字母。
题解2
class Solution {private Map<Character, String> phone = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<String>();if (digits.length() == 0) {return res;}backtrack(digits, 0, new StringBuilder(), res);return res;}private void backtrack(String digits, int index, StringBuilder combination, List<String> res) {if (index == digits.length()) {res.add(combination.toString());return;}char digit = digits.charAt(index);String letters = phone.get(digit);for (int i = 0; i < letters.length(); i++) {combination.append(letters.charAt(i));backtrack(digits, index + 1, combination, res);combination.deleteCharAt(index);}}
}
执行结果

相关文章:
[Java·算法·中等]LeetCode17. 电话号码的字母组合
每天一题,防止痴呆题目示例分析思路1题解1分析思路2题解2题目 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。…...
C#7/C#8/C#9 与dotnetSDK 以及dotnet framework对应关系
语言版本 对应的.net framework版本 对应的.net sdk版本 推荐使用的vs studio C#7.3 3.5、 4.0、 4.5 、4.5.1、 4.5.2 、4.6 、4.6.1、 4.6.2 4.7.1、 4.7.2 .netcore 2.0、.netcore2.1、 .netcore2.2 C#8.0 / F#4.7 不支持 .netcore 3.0、.netcore 3.1 C# 9.0 …...
jvm调优经验总结
最近一段时间很忙,忙到每天10点多11点下班还是感觉有很多事没有做完,不过倒也没有什么太过低落的情绪,有时候只安静的看一个视频,简单看点文字,或者平静的坐着,并没有太多想法。短时间的工作压力是可以接受…...
等保合规知识常见问题解答
Q1:什么是等级保护? 答:等级保护是指对国家重要信息、法人和其他组织及公民的专有信息以及公开信息和存储、传输、处理这些信息的信息系统分等级实行安全保护,对信息系统中使用的信息安全产品实行按等级管理,对信息系统…...
分享5款Windows同类软件中的翘楚
今天要给大家推荐的是5款软件,每个都是同类软件中的个中翘楚,请大家给我高调地使用起来,不用替我藏着掖着。1.沙盒工具——Sandboxie Sandboxie是一个电脑必备的沙盘工具,对于从网上下载的软件安装包、文件、视频、图片等等一切不…...
记--springboot-工具类中使用@Component、@Resource与@Value失效
写一个工具类 需要使用Resource注入RedisTemplate 使用Value获取application.properties配置文件中配置 并使用Component将该工具类交个spring管理 调试的时候RedisTemplate以及所有的变量全是是null 看了网上的各种解决方式五花八门 有的说出现问题的原因:Compon…...
手写一个react,看透react运行机制
适合人群 本文适合0.5~3年的react开发人员的进阶。 讲讲废话: react的源码,的确是比vue的难度要深一些,本文也是针对初中级,本意让博友们了解整个react的执行过程。 写源码之前的必备知识点 JSX 首先我们需要了解什么是JSX。…...
JS判断输入值是否为正整数,判断变量是否为数字
这篇文章将讨论如何确定一个变量是否代表 JavaScript 中的有效数字。 1.JS中的test是原来是JS中检测字符串中是否存在的一种模式,JS输入值是否为判断正整数代码: <script type”text/javascript”> function test() { var num document.getElem…...
Android开发八股文,Android也有自己的八股文了
前言别的行业都有自己的八股文,凭什么Android没有。2023春招即将来临,很多同学会问 Android开发的面试题有必要背吗?我的回答是:很有必要。你可以讨厌这种模式,但你一定要去背,因为不背你就进不了大厂。国内…...
你需要同款“Unreal项目自动化编译、打包和部署”方案吗?
在过往几期的UWA Pipeline最佳实践案例中,我们分享了如何通过Pipeline实现性能优化、性能管理、游戏内容验收和云真机系统的应用(实现批量真机设备的自动化测试,以及针对特效性能优化的方式),其实这些高效的方法并不局…...
电子技术——CMOS-AB类输出阶
电子技术——CMOS-AB类输出阶 本节我们研究CMOS-AB类输出阶。 经典配置 下图展示了一个经典的CMOS-AB类输出阶: 这个很像BJT二极管偏置版本的AB类输出阶,在这里二极管偏置变成了 Q1Q_1Q1 和 Q2Q_2Q2 偏置。不想BJT的情况,这里 QNQ_NQN…...
2023王道考研数据结构笔记第二章线性表
第二章 线性表 2.1 线性表的定义 2.1.1 线性表的基本概念 线性表是具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n0时线性表是一个空表。若用L命名线性表,则其一般表示为: L(a1,a2,...,ai,ai1,...,an)L(a_1…...
[chapter 11][NR Physical Layer][Layer Mapping]
前言:这里参考Curious Being系列 ,简单介绍一下NR 5G 物理层核心技术层映射.我们主要讲了一下what is layer Mapping, why need layer Mapping, how layer Mapping 参考文档:3GPP 38.211- 6.3.1.3 Layer mapping《5G NR Physical Layer | Cha…...
什么是工业物联网(IIoT)?
什么是工业物联网(IIoT)?工业物联网(IIoT) 被定义为一组设备和应用,允许大企业创建从核心到边缘的端到端连接环境。其还包括传统的物理基础设施,如集装箱和物流卡车,以收集数据,对事件做出反应,并在智能设备的帮助下做…...
「TCG 规范解读」PC 平台相关规范(4)
可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alli…...
CSS背景属性之颜色渐变
颜色渐变 颜色渐变其实在网页设计中并不是特别常见, 但也不可避免的会出现导航栏是渐变色这种情况或者别的不是单一颜色的情况, 例如:这样的设计解决方案并不是只可以使用颜色渐变,我们可以使用两个div拼接,将文字放…...
IPv4地址细讲
文章目录一、IPv4地址简介二、IPv4地址的表示方法点分十进制记法三、IP地址的分类四、特殊IPv4地址:全 “0” 和全 “1”五、常用的三类IP地址使用范围六、五类IP地址的范围一、IPv4地址简介 IPv4地址分5类,每一类地址都由固定长度的字段组成࿱…...
sql语句中exists用法详解
文章目录一、语法说明exists:not exists:二、常用示例说明1.查询a表在b表中存在数据2.查询a表在b表中不存在数据3.查询时间最新记录4.exists替代distinct剔除重复数据总结一、语法说明 exists: 括号内子查询sql语句返回结果不为空ÿ…...
思迅软件端口不通导致软件和软锁报错的问题
一、端口不通导致软件和软锁报错的问题 问题说明:打开软件提示到:xxx.xxx.xxx.xxx失败! 处理步骤1: 假设软锁服务器IP为192.168.0.1,分别在服务器本机和客户端电脑测试软锁服务: 在服务器的浏览器中访问地址: http:/…...
Docker之路(7.DockerFile文件编写、DockerFile 指令解释、CMD与ENTRYPOINT的区别)
1.DockerFile介绍 dockerfile 是用来构建docker镜像的文件!命令参数脚本! 构建步骤: 编写一个dockerfile文件docker build构建成为一个镜像docker run 运行镜像docker push发布镜像(DockerHub、阿里云镜像仓库) 2.Dock…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
