当前位置: 首页 > 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 照片图像编辑器

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

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...