力扣17-电话号码的数字组合
力扣17-电话号码的数字组合
- 思路
- 代码
题目链接
思路

原题:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”
思路:
电话号码中的一个数字可以对应到多个字母,例如2对应a、b、c。要求23对应的字母组合,就是把2和3对应的字母进行组合。
在每次组合的过程中,一个数字只能取一个字母,不能连续两个字母来自同一个数字;
思考:
问题1:如何收集一个可能的组合?
问题2:在收集到一种组合后,如何继续收集第二种组合?
对于问题1:用暴力法可以解决,每层循环枚举一个数字对应的字母,但是电话号码串很长,循环嵌套深,代码不易好编写
可以采用递归的方式,每层进入递归函数,尝试一个数字对应的点好号码
进入函数,可以想向成进入一棵树的下一层,当递归的深度到达电话号码长度,即到达叶子节点,则返回。
问题3:在递归的每一层做什么?
递归纵向是进入树下一层,即电话号码中的一个数字,在同一层,应该去枚举这个数字对应的字母,这样就可以将当前层的字母,与上一层的字母进行结合,形成答案的一部分,,
问题4:递归什么时候结束?
到达电话号码的长度时,应该往树的上一层返回。
这里的往下递,和往上归,即回溯法,往下遍历是搜索,往上是回溯;回退到上一层,当前数字对应的字母就丢弃了,
比如 2,3; 3是第二层,遍历得到的字母组合是ab, 已经达到电话号码长度,往上一层回溯时b应该就被丢弃。
因此,本题使用回溯法,纵向遍历电话号码中的每个数字,横向遍历每个数字对应的字母,达到电话号码长度时收集一种组合,并往上一层回溯。
代码
class Solution {private List<String> ans;private String[][] dic = {{"2","abc"},{"3","def"},{"4","ghi"},{"5","jkl"},{"6","mno"},{"7","pqrs"},{"8","tuv"},{"9","wxyz"}};public List<String> letterCombinations(String digits) {ans = new ArrayList<>();if (digits.length()==0) {return ans;}Map<String,String> m = new HashMap<>();for (int i=0, n=dic.length; i<n; i++) {m.put(dic[i][0]+"", dic[i][1]+"");}String path = "";dfs(digits, m, 0, path);return ans;}public void dfs(String digits, Map<String, String> mp, int i, String path) {int n = digits.length();if (i>=n) {ans.add(new String(path));return;}String t = mp.get(digits.charAt(i)+"");for (int j=0, m=t.length(); j<m; j++) {dfs(digits, mp, i+1, path+t.charAt(j));}}
}
相关文章:
力扣17-电话号码的数字组合
力扣17-电话号码的数字组合 思路代码 题目链接 思路 原题: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 输…...
如何处理模型的过拟合和欠拟合问题
好久没有写人工智能这块的东西了,今天正好在家休息,给大家分享一下最近在训练时遇到的过拟合和欠拟合的问题,经过仔细的思考,总结如下: 在处理模型的过拟合和欠拟合问题时,我们需要根据具体情况采取不同的…...
CSRF详解
CSRF,全称是Cross-Site Request Forgery,即跨站请求伪造,也被称为“one click attack”或者session riding,是一种网络攻击方式。它允许攻击者诱导用户在已登录的Web应用程序上执行非预期的操作。 工作原理CSRF攻击通常涉及三个主…...
C# winform 的数据采集,采集周期是间隔10ms、100ms等等,但始终都有1ms的误差,并不是精准的10ms,哪些原因呢
C# winform 的数据采集,采集周期是间隔10ms、100ms等等,但始终都有1ms的误差,并不是精准的10ms,哪些原因呢 在C# WinForms应用程序中进行数据采集时,如果遇到采集周期存在1ms误差的问题,可能的原因包括&am…...
【国内中间件厂商排名及四大中间件对比分析】
国内中间件厂商排名 随着新兴技术的涌入,一批国产中间件厂商破土而出,并在短时间内迅速发展,我国中间件市场迎来洗牌,根据市占率,当前我国中间件厂商排名依次为:东方通、宝兰德、中创股份、金蝶天燕、普元…...
qt QLocale详解
1、概述 QLocale是Qt框架中的一个类,用于处理与本地化相关的操作。它能够方便地实现日期、时间、数字和货币的格式化和解析,支持不同的语言、区域设置和字符集。QLocale提供了一种跨平台的方式来获取当前系统的语言设置,并返回该语言的本地化…...
Node.js简介以及安装部署 (基础介绍 一)
Node.js简介 Node.js是运行在服务端的JavaScript。 Node.js是一个基于Chrome JavaScript运行时建立的一个平台。 Node.js是一个事件驱动I/O服务端JavaScript环境,基于Google的V8引擎,V8引擎执行Javascript的速度非常快,性能非常好。 Node.…...
unity实习面
天津小厂 23分钟 下午三点约的面 一直到三点15才面上 估计前边也是在面别人然后面的时间有点长了 唉小厂也是一堆人 上来直接说看项目代码 给看了一下经典tankgame 主要是问了一些其中的代码是什么意思 然后问对象池怎么用 答:光知道不会用 问生命周期函数 得…...
React Native WebView 进阶:实现带回调函数的通讯
实现带回调的通讯 Web 端实现 在网页中,我们使用 window.callbacks 对象来注册回调函数,并将 callbackId 传递给 App: <script>window.callbacks {callbacks: {},register: function(successCallback, errorCallback) {const callb…...
【设计模式】结构型模式(四):组合模式、享元模式
《设计模式之结构型模式》系列,共包含以下文章: 结构型模式(一):适配器模式、装饰器模式结构型模式(二):代理模式结构型模式(三):桥接模式、外观…...
分布式数据库中间件mycat
MyCat MyCat是一个开源的分布式数据库系统,它实现了MySQL协议,可以作为数据库代理使用。 MyCat(中间件)的核心功能是分库分表,即将一个大表水平分割为多个小表,存储在后端的MySQL服务器或其他数据库中。 它不仅支持MySQLÿ…...
放大电路中的反馈 > 负反馈 > 四种组态 > 虚断和虚短
零、什么是反馈?为什么反馈很重要?而且负反馈最重要? 反馈在所有领域都是很美的东西: 公司出台某项政策,过了一个月让大家谈谈新政策的感受,然后公司对政策进行适当调整。 高三月考可以反应你对各个学课的…...
STM32F405RGT6单片机原理图、PCB免费分享
大学时机创比赛时画的板子,比到一半因为疫情回家,无后续,,,已打板验证过,使用stm32f405rgt6做主控 下载文件资源如下 原理图文件 pcb文件 外壳模型文件 stm32f405例程 功能 以下功能全部验证通过 4路…...
大语言模型鼻祖Transformer的模型架构和底层原理
Transformer 模型的出现标志着自然语言处理(NLP)技术的一次重大进步。这个概念最初是针对机器翻译等任务而提出的,Transformer 后来被拓展成各种形式——每种形式都针对特定的应用,包括原始的编码器-解码器(encoder-de…...
GB/T 43206—2023信息安全技术信息系统密码应用测评要求(五)
文章目录 附录AA.1 概述A.2 密钥产生A.3 密钥分发A.4 密钥存储A.5 密钥使用A.6 密钥更新A.7 密钥归档A. 8 密钥撤销A.9 密钥备份A.10 密钥恢复A.11 密钥销毁 附录B附录C 附录A A.1 概述 密钥管理对于保证密钥全生存周期的安全性至关重要 ,可以保证密钥(除公开密钥外) 不被非授…...
深度学习:BERT 详解
BERT 详解 为了全面详细地解析BERT(Bidirectional Encoder Representations from Transformers),我们将深入探讨它的技术架构、预训练任务、微调方法及其在各种自然语言处理(NLP)任务中的应用。 一、BERT的技术架构 …...
智能的编织:C++中auto的编织艺术
在C的世界里,auto这个关键字就像是一个聪明的助手,它能够自动帮你识别变量的类型,让你的代码更加简洁和清晰。下面,我们就来聊聊auto这个关键字的前世今生,以及它在C11标准中的新用法。 auto的前世 在C11之前&#x…...
订单分库分表
一、引言 在当今互联网时代,随着电商、金融等行业的快速发展,订单数量呈爆炸式增长。传统的单一数据库存储订单信息的方式面临着巨大的挑战,如数据存储容量有限、查询性能下降、数据备份和恢复困难等。为了解决这些问题,分库分表技…...
【温度表达转化】
【温度表达转化】 C语言代码C代码Java代码Python代码 💐The Begin💐点点关注,收藏不迷路💐 利用公式 C5∗(F−32)/9 (其中C表示摄氏温度,F表示华氏温度) 进行计算转化。 输出 输出一行&#x…...
封装一个web Worker 处理方法实现多线程
背景: 开启多线程处理一段耗时的逻辑 简化Worker使用 直接上代码: 以下是封装的函数直接复制即可 /*** 封装一个worker的启动函数 用于开启一个新的线程 来处理一些耗时的操作* param {object} paremdata 传递给worker的参数* param {function} call…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
