当前位置: 首页 > news >正文

Leetcode 17.电话号码的字母组合

目录

题目

方法一

思路

代码


题目

17. 电话号码的字母组合

难度:中等

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

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

示例 1:

输入:digits = "23"

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

示例 2:

输入:digits = ""

输出:[]

示例 3:

输入:digits = "2"

输出:["a","b","c"]

方法一

思路

这是一个经典的回溯问题,我们先来分析一下这道题的暴力解法。暴力解法很容易想到,通过给定的字符串的数字个数和每个数字对应的字母,我们使用循环遍历,然后存储下来加入返回数组,这是一个简单的穷举算法。

我们可以使用回溯算法优化,每个回溯算法都可以抽象为树形结构。

  • 根节点:代表算法的起始点,没有任何决策,相当于回溯树的顶部。

  • 分支:从每个节点延伸出的边表示可能的决策或选择。在选择一个选项后,算法沿着相应的分支向下移动到树的下一层。

  • 叶子节点:代表算法的最终状态,通常是找到了问题的解或者是达到了问题空间的边界。

  • 回溯边:当算法在某个分支上探索到尽头(即该路径不是解的一部分)时,它会通过回溯边返回到上一个决策点,尝试其他选项。

  • 深度优先搜索:回溯算法通常采用深度优先搜索(DFS)策略,即尽可能深地探索树的分支,直到找到解或确定该分支不包含解。

  • 剪枝:在某些情况下,可以提前判断某个分支不可能是解的一部分,从而剪掉这个分支,减少不必要的计算。

  • 路径:从根节点到叶子节点的路径代表一个完整的解决方案,或者在电话号码的字母组合问题中,代表一个完整的字母组合。

  • 状态存储:在树的每个节点上,都需要存储足够的状态信息,以便在回溯时能够恢复到之前的决策状态。

以本题为例,树的根节点没有字母,每个数字对应一层,每层的节点数等于该数字可以映射到的字母数。从每个节点延伸出的边代表选择一个特定的字母,叶子节点代表一个完整的字母组合。 

以字符串 "23" 为例,他对应的回溯树结构如下:

我们用递归模拟树的遍历,在遍历到每层结点时将其加入字符串。在递归到递归出口时就是遍历到叶子结点,此时就是完整组合。我们将其加入返回数组。

以为我们要的是全部组合,所以不需要剪枝。

在递归返回后我们会从字符串中弹出一个字符,对应的是回溯的过程。

代码

class Solution {
public:string s;vector<string> board={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void dfs(int index,string& digits,vector<string>& ret){if(index == digits.size()){ret.push_back(s);return;}int z=digits[index]-'0';for(int i=0;i<board[z].size();i++){s.push_back(board[z][i]);//递归dfs(index+1,digits,ret);//回溯s.pop_back();}}vector<string> letterCombinations(string digits) {vector<string> ret;if(digits.empty()){return ret;}dfs(0,digits,ret);return ret;}
};

注意:在 letterCombinations 如果digits为空需要返回,不然在 dfs中会加入一个空串。

相关文章:

Leetcode 17.电话号码的字母组合

目录 题目 方法一 思路 代码 题目 17. 电话号码的字母组合 难度&#xff1a;中等 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对…...

位1的个数

编写一个函数&#xff0c;获取一个正整数的二进制形式并返回其二进制表达式中设置位的个数&#xff08;也被称为汉明重量&#xff09;。 示例 1&#xff1a; 输入&#xff1a;n 11 输出&#xff1a;3 解释&#xff1a;输入的二进制串 1011 中&#xff0c;共有 3 个设置位。示…...

RPA在政务服务中的挑战与解决方案

随着数字化时代的到来&#xff0c;数字政务的建设已成必然趋势&#xff0c;RPA作为数字化转型的重要工具之一&#xff0c;能够帮助政府单位快速实现业务流程的自动化和智能化&#xff0c;提高工作效率和质量&#xff0c;为建设数字政务提供强有力的支持&#xff0c;因此正被越来…...

RabbitMQ docker安装

后台配置文件 rabbitmq:image: rabbitmq:latestcontainer_name: rabbitmqports:- "5672:5672" # RabbitMQ server port- "15672:15672" # RabbitMQ management console portenvironment:RABBITMQ_DEFAULT_USER: adminRABBITMQ_DEFAULT_PASS: admin 若要打…...

关于vs调试的一些基本技巧方法,建议新手学习

文章目录 1.Debug 和 Release2.VS的调试快捷键3.对程序的监视和内存观察3.1监视3.2内存 4.编程常见错误归类4.1编译型错误4.2链接型错误4.3运行时错误 1.Debug 和 Release 在我们使用的编译器 vs 中&#xff0c;这个位置有两个选项&#xff0c;分别为Debug和Release&#xff0c…...

​MySQL——索引(二)创建索引(2)使用 CREATE INDEX 语句在已经存在的表上创建索引

若想在一个已经存在的表上创建索引&#xff0c;可以使用 CREATE INDEX 语句&#xff0c;CREATEINDEX语句创建索引的具体语法格式如下所示: CREATE [UNIQUEIFULLTEXTISPATIAL]INDEX 索引名 ON 表名(字段名[(长度)J[ASCIDESC]); 在上述语法格式中&#xff0c;UNIQUE、FULLTEXT 和…...

前端HTML总结

目录 前言 正文 head SEO body 网页的主要组成元素&#xff1a; body标签中常见的标签&#xff1a; 自闭合标签&#xff1a; 无语义标签&#xff1a; 特殊符号&#xff1a; 列表 子项&#xff1a; 样式修改&#xff1a; 定义列表&#xff1a; 语义化&#xff1…...

【动态规划】647. 回文子串

力扣链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 动规大法开始吟唱&#xff1a; dp[i][j]含义&#xff1a;从i到j的子串是否为回文子串 递推公式&#xff1a;当s[i] s[j]时 1. j-i<1时, dp[i][j]为true 2. 否则&#xff0c;若dp[i1][j-1]为true&#x…...

python-约瑟夫环(赛氪OJ)

[题目描述] n 个人&#xff08; 0,1,2,3,4...n−1 &#xff09;&#xff0c;围成一圈&#xff0c;从编号为 k 的人开始报数&#xff0c;报数报到 m 的人出队。 下次从出队的人之后开始重新报数&#xff0c;循环往复&#xff0c;当队伍中只剩最后一个人的时候&#xff0c;那个人…...

Less 教程:从入门到精通

Less 教程&#xff1a;从入门到精通 1. 引言 Less 是一种流行的动态样式表语言&#xff0c;它扩展了 CSS 的功能&#xff0c;使其更加强大和灵活。通过本教程&#xff0c;我们将深入探讨 Less 的基本概念、特性以及如何在项目中实际应用它。 2. Less 的基本概念 2.1 变量 …...

【VScode】如何在anaconda虚拟环境中打开vscode项目

文章目录 【必备知识】打开anaconda虚拟环境切换到项目工作目录激活anaconda虚拟路径让vscode从当前目录打开 【必备知识】 anaconda环境变量配置及配置python虚拟环境 https://blog.csdn.net/xzzteach/article/details/140621596 打开anaconda虚拟环境 切换到项目工作目录 …...

Flink任务提交流程和运行模式

任务提交流程 Flink 的提交流程随着部署模式、资源管理平台的不同&#xff0c;会有不同的变化。这里做进一步的抽象&#xff0c;形成一个大概高视角的任务执行流程图&#xff0c;如下&#xff1a; Flink按照集群和资源管理的划分运行模式有&#xff1a;Standalone、Flink On…...

【机器学习】 Sigmoid函数:机器学习中的关键激活函数

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 Sigmoid函数&#xff1a;机器学习中的关键激活函数1. 引言2. Sigmoid函数定义3.…...

Vue+Element Plus后台管理主界面搭建实现

​ 续接Django REST Framework&#xff0c;使用Vite构建Vue3的前端项目 1. 后台管理系统主界面框架搭建 后台系统主界面搭建 新建后台管理文件目录 完成后台整体布局 // 1.主界面 index.vue<script setup lang"ts"></script><template><el-…...

JAVA—异常

认识异常&#xff0c;学会从报错信息中发现问题&#xff0c;解决问题。并学会构建自定义异常&#xff0c;提醒编程时注意 目录 1.认识异常 2.自定义异常 1.自定义运行时异常 2.自定义编译时异常 3.异常的处理 1.认识异常 异常就是代表程序出现的问题&#xff0c;用来查询B…...

常见八股面试题:Dubbo 和 Spring Cloud Gateway 有什么区别?

大家好&#xff0c;我是鸭鸭&#xff01; 此答案节选自鸭鸭最近弄的面试刷题神器面试鸭&#xff0c;更多大厂常问面试题&#xff0c;可以点击进行阅读哈&#xff01; 目前这个面试刷题神器刚出&#xff0c;有网页和小程序双端可以阅读&#xff01; 回归面试题&#xff01; …...

k8s分布式存储-ceph

文章目录 Cephdeploy-ceph部署1.系统环境初始化1.1 修改主机名&#xff0c;DNS解析1.2 时间同步1.3 配置apt基础源与ceph源1.4关闭selinux与防火墙1.5 **创建** ceph **集群部署用户** cephadmin1.6分发密钥 2. ceph部署2.1 **安装** ceph 部署工具2.2 **初始化** mon **节点**…...

Redis cluster集群部署

redis搭建集群模式、Cluster模式&#xff08;6节点&#xff0c;3主3从集群模式&#xff0c;添加删除节点&#xff09;_redis cluster节点带数据增减-CSDN博客...

Java泛型的理解

前言 泛型是Java中一个比较重要的特性&#xff0c;是于JDK5引入新特性&#xff0c;其主要目的是为了提供编译时的类型安全检测机制和简化代码。本文主要探讨一下泛型的使用。 假如说没有泛型 假如说没有泛型&#xff0c;可以举一个例子&#xff1a; ArrayList list new Ar…...

Linux 照片图像编辑器

前言 照片图像编辑器是一种软件程序,它允许用户对数字照片或图像进行各种编辑和修改。以下是一些常见的功能及其解释: 裁剪与旋转 : 裁剪:移除图像的某些部分,以改善构图或符合特定尺寸要求。旋转:改变图像的方向,可以校正歪斜的照片或者为了艺术效果而旋转。调整亮度…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...