力扣第17题 电话号码的字母组合 c++ 回溯 经典提升题
题目
17. 电话号码的字母组合
中等
相关标签
哈希表 字符串 回溯
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = "" 输出:[]
示例 3:
输入:digits = "2" 输出:["a","b","c"]
提示:
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
思路和解题方法
- 代码首先定义了一个常量数组
letterMap,其中每个元素表示数字0-9对应的字符集合。这样,我们可以通过数字来索引letterMap中的元素,得到对应的字符集合。- 接下来,代码定义了两个成员变量
ans和s,分别用于存储最终的答案集合和临时的组合结果。- 然后,代码定义了一个递归函数
backtracking,该函数通过参数digits和index来表示当前处理的数字串和目前处理到的位置。- 在
backtracking函数中,当index等于digits的大小时,说明已经找到了一种组合,将s加入到答案集合ans中,并返回。- 否则,获取当前位置的数字
digit,以及它对应的字符集合letters。- 接下来,通过循环遍历当前数字对应的每个字符,并将其依次加入到临时组合结果字符串
s中。- 然后,递归调用
backtracking函数处理下一个数字的字母组合。- 最后,在完成递归调用后,进行回溯操作,将刚才加入的字符移出,继续尝试下一个字符。
- 在主函数
letterCombinations中,首先清空临时字符串s和答案集合ans。- 然后,判断输入的数字串是否为空,如果为空,直接返回空的答案集合。
- 否则,调用
backtracking函数开始搜索字母组合。- 最后,返回最终的答案集合。
复杂度
时间复杂度:
O(3m×4n)
算法的时间复杂度为 O(3m×4n),其中 m 表示输入数字串中对应字母集合大小为 3 的数字个数,n 表示输入数字串中对应字母集合大小为 4 的数字个数。因为一般情况下一个数字对应 3 个字母,另外两个数字对应 4 个字母,所以总的时间复杂度为 O(3m×4n)。
空间复杂度
O(m+n)
空间复杂度为 O(m+n),即递归栈的深度。在最坏情况下,所有数字都对应字母集合大小为 4,所以根据上面的时间复杂度分析,有 m+n 个数字需要进行搜索,因此栈的深度也为 m+n,所以空间复杂度为 O(m+n)。
c++ 代码
class Solution {
public:const string letterMap[10]={"", // 数字0对应的字母为空字符串,因为通常没有字母对应数字0"", // 数字1对应的字母为空字符串,因为通常没有字母对应数字1"abc", // 数字2对应的字母为abc"def", // 数字3对应的字母为def"ghi", // 数字4对应的字母为ghi"jkl", // 数字5对应的字母为jkl"mno", // 数字6对应的字母为mno"pqrs", // 数字7对应的字母为pqrs"tuv", // 数字8对应的字母为tuv"wxyz" // 数字9对应的字母为wxyz};vector<string> ans; // 存储最终的答案集合string s; // 用于临时存储每个组合结果的字符串void backtracking(string &digits,int index){if(index == digits.size()) // 如果达到了数字串的末尾,说明已经找到了一种组合,将其加入到答案集合中{ans.push_back(s);return ;}int digit = digits[index] - '0'; // 获取当前位置的数字string letters = letterMap[digit]; // 获取当前数字对应的字母集合for(int i=0;i<letters.size();i++) // 遍历当前数字对应的每个字母{s.push_back(letters[i]); // 将字母加入到临时组合结果字符串中backtracking(digits,index +1); // 继续递归下一个数字的字母组合s.pop_back(); // 回溯,将刚才加入的字母去除,尝试下一个字母}}vector<string> letterCombinations(string digits) {s.clear(); // 清空临时字符串sans.clear(); // 清空答案集合ansif(digits.size() == 0) // 如果输入的数字串为空,则直接返回空的答案集合{return ans;}backtracking(digits,0); // 开始回溯搜索字母组合return ans; // 返回最终的答案集合}
};
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
相关文章:
力扣第17题 电话号码的字母组合 c++ 回溯 经典提升题
题目 17. 电话号码的字母组合 中等 相关标签 哈希表 字符串 回溯 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。…...
华纳云:怎么判断VPS的ip是不是公网ip
要判断一个VPS的IP地址是否为公网IP,您可以执行以下步骤: 查看IP地址: 首先,获取您的VPS的IP地址。您可以使用以下命令来查看VPS的IP地址: curl ifconfig.me 或 curl ipinfo.io/ip 这些命令将显示VPS的公网IP地址。 检…...
QT学习笔记1-Hello, QT
1. QT环境 1.1 QT_CREATOR QT的集成开发工具,可以进行项目的创建运行。有一些实例可以运行之。 1.2 QT_ASSISTANT QT的工具书 2. 核心的概念 2.1 windows 窗口 2.2 widget 组件放置在窗口上的 2.3 bar 栏 2.4 icon 图标 3. Hello, QT 3.1 main.cpp …...
水滴卡片效果实现
效果展示 CSS 知识点 border-radius 属性运用 FANCY-BORDER-RADIUS 工具 此工具主要是实现不规则的图形。 FANCY-BORDER-RADIUS 工具地址 页面整体布局实现 <div class"container"><div class"drop" style"--clr: #ff0f5b">&l…...
【算法题】2899. 上一个遍历的整数
插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 坚持不懈,越努力越幸运,大家一起学习鸭~~~ 题目: 给你一个下标从 0 开始的字符串数组…...
Python+unittest+requests接口自动化测试框架搭建 完整的框架搭建过程
首先配置好开发环境,下载安装Python并下载安装pycharm,在pycharm中创建项目功能目录。如果不会的可以百度Google一下,该内容网上的讲解还是比较多比较全的! 大家可以先简单了解下该项目的目录结构介绍,后面会针对每个文…...
系统架构设计:19 论数据挖掘技术的应用
目录 一 数据挖掘技术 1 数据挖掘的分类 2 数据挖掘的主要方法 一 数据挖掘技术 从技术角度看,数据挖掘可以定义为从大量的、不完全的、有噪声的、模糊的、随机的实际数据中提取隐含在其中的、人们不知道的、但又潜在有用的信息和知识的过程。</...
如何选择高防CDN和高防IP?
目录 前言 一、对高防CDN的选择 1. 加速性能 2. 抗攻击能力 3. 全球覆盖能力 4. 可靠性和稳定性 二、对高防IP的选择 1. 防御能力 2. 服务质量 3. 安全性 4. 价格 三、高防CDN和高防IP的优缺点对比 1. 高防CDN的优缺点 2. 高防IP的优缺点 总结 前言 随着互联网…...
【html】利用生成器函数和video元素,取出指定时间的视频画面
简言 有的时候想截取视频某一秒的视频画面。 手动截取操作麻烦,还得时刻关注视频播放时间。 于是,我搞出来了一个根据视频自动截取特定时间描述的页面。 效果 实现步骤 获取视频对象根据视频时长生成时间选择表单根据表单选择的时间和视频地址&#x…...
第五十九章 学习常用技能 - 将数据从一个数据库移动到另一个数据库
文章目录 第五十九章 学习常用技能 - 将数据从一个数据库移动到另一个数据库 第五十九章 学习常用技能 - 将数据从一个数据库移动到另一个数据库 如果需要将数据从一个数据库移动到另一个数据库,请执行以下操作: 识别包含数据及其索引的Global。 如果…...
虚拟示波器的设计与实现
摘 要 针对传统示波器功能单一、不方便更新升级的缺陷,本文基于虚拟仪器软件LabVIEW和NI PCI-6221数据采集卡设计并实现了一种多功能虚拟示波器,该虚拟示波器不仅具有采集和显示实际信号时域波形的功能,还具有信号产生、波形存储等功能。 测试…...
ImgPlus:基于CodeFormer的图片增强
背景 最近参与了华为云开发者大会AI赛道,做了一个AI图片增强作品,本片文章来简单介绍一下。 正文 作品名称:ImgPlus 赛题技术领域选择: AI,图片增强 使用技术名称: CodeFormer,ECS࿰…...
2024华为校招面试真题汇总及其解答(二)
6.【算法题】三步问题 题目: 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。 示例1: 输入:n = 3 输出:4说明: 有四种走法示例2: 输入:n = 5输出:1…...
编译链接(Compile Link)
文章目录 前言一、翻译环境1、概念2、翻译环境的组成3、什么是编译链接? 二、编译1、编译的阶段2、预编译3、编译1、什么是语法分析?2、什么是词法分析?3、什么是语义分析?4、什么是符号汇总? 4、汇编1、符号表展示 三…...
14 幂等生产者和事务生产者
kafka消息交付可靠性保障和精确一次语义处理 消息交付可靠性保障,指的kafka对Producer和Consumer要处理的消息提供什么样的承诺。总共就三种:at most once 、at least once、axactly once kafka默认提供的是 at least once。原因是只有Broker提交消息并…...
zabbix部署与监控
目录 一、什么是zabbix? 二、zabbix 监控原理 三、Zabbix 新特性 三、Zabbix 功能组件 四、部署 zabbix zabbix的服务端部署 zabbix的客户端部署 zabbix的服务端部署 一、什么是zabbix? zabbix 是一个基于 Web 界面的提供分布式系统监视以及网络…...
Python 编程基础 | 第五章-类 | 5.8、运算符重载
一、运算符重载 1、Python类内置方法 Python常用内置方法,如下: __init__: 构造函数,在生成对象时调用__del__: 析构函数,释放对象时使用__repr__: 打印,转换__setitem__࿱…...
【前端设计模式】之解释器模式
解释器模式是一种行为设计模式,它用于解释特定语言或规则的表达式。在前端开发中,解释器模式可以用于处理复杂的逻辑或规则,并将其转化为可执行的代码。 解释器模式特性 定义语言规则:解释器模式通过定义语言规则来解析和执行表…...
TiDB 7.4 发版:正式兼容 MySQL 8.0
MySQL 是全球最受欢迎的开源数据库,长期位于 DB-Engines Ranking 排行榜第二名,在世界范围内拥有数量庞大的企业用户和开发者。然而,随着时间的推移,MySQL 用户正面临新挑战。Oracle 官宣将在 2023 年 10 月终止 MySQL 5.7 版本的…...
QT 网络编程 服务端 客户端 QTcpServer
服务端的创建 //创建服务端QTcpServer对象 server new QTcpServer(this);//设置服务端,端口,这里绑定的是主机的所有网卡, server->listen(QHostAddress::Any, 8080);//绑定连接信号与槽 connect(this->server, &QTcpServer::new…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
