力扣第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 <= 4
digits[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…...

Stm32_标准库_16_串口蓝牙模块_手机与蓝牙模块通信_手机传入信息能对芯片时间日期进行更改
实现了手机发送信息给蓝牙模块,程序对数据进行分析拆解,并更新自身数据 main.c: #include "stm32f10x.h" // Device header #include "Delay.h" #include "OLED.h" #include "Serial.h" #include "Ti…...

137.【SpringCloud-快速搭建】
微服务框架搭建 (一)、SpringCloud-Parent1.创建一个SpringBoot项目2.导入我们的依赖 (二)、SpringCloud-API (实体类)1.创建一个SpringBoot项目2.导入我们的依赖3.创建我们的实体类 (三)、SpringCloud-dept (业务A)1.创建一个SpringBoot项目2.导入我们的依赖3.配置我们的配置信…...

计算机网络第2章-CDN(4)
视频流和内容分发网 HTTP流和DASH 在HTTP流中,视频只是存储在HTTP服务器中作为一个普通的文件,每个文件有有一个特定的URL。当用户要看视频时,客户与服务器之间创建一个TCP连接并发送HTTP GET请求。 HTTP流具有严重缺陷,即所有…...

Linux常见的指令合集
Linux指令合集 认识linuxlinux基础指令1.pwd 命令2. ls 命令3.cd 命令4. man 命令5. grep 命令6. ps 命令7. kill 命令8. netstat 命令9. date 查看当前系统时间10. echo 打印选项 -e linux文件操作指令1. mkdir 命令2. rmdir 命令3. touch 命令4. rm 命令5. mv 命令6. cp 命令…...

字符串_哈希
参考文章: E. Compress Words(字符串hash)_z听歌的小孩z的博客-CSDN博客 字符串哈希 - OI Wiki (oi-wiki.org) 板子: #include<bits/stdc.h> using namespace std; const int N2e450; typedef long long ll; const int mod1e97; typedef unsig…...

python 之enumerate()函数
文章目录 enumerate() 是 Python 中的一个内置函数,它用于在遍历可迭代对象(如列表、元组、字符串等)时同时获取每个元素的索引和值。这个函数非常有用,因为它允许您在迭代过程中轻松地访问元素的索引,而不需要手动维护…...

【LeetCode刷题(数据结构与算法)】:用队列实现栈
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty) 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶 int pop() 移除并返回栈顶元素 int top() 返…...

“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递的方式的区别
“客户端到服务器的数据传递”和“服务器上的数据传递”这两种数据传递方式的主要区别如下: 数据的流动方向: 在“客户端到服务器的数据传递”中,数据是从客户端(如浏览器)流向服务器。在“服务器上的数据传递”中&…...

LCR 181 字符串中的单词反转
题目来源: leetcode题目,网址:LCR 181. 字符串中的单词反转 - 力扣(LeetCode) 解题思路: 倒叙遍历,获得每个单词的起始位置与终止位置,然后将每次遇到的单词插入结果中。 解题…...

百度OCR识别图片文本字符串——物联网上位机软件
一、开发背景 根据项目需求,我们需要完成LED显示屏实时显示歌词的效果。最优的方法是调用歌曲播放器的API获取歌词,但是由于这个开发资格不是很好申请,因此我们采用其他方案,即通过OCR识别获取歌词,并投射到LED显示屏上…...