【practise】电话号码的字母组合

关于我:在这里插入图片描述


睡觉待开机:个人主页

个人专栏: 《优选算法》《C语言》《CPP》
生活的理想,就是为了理想的生活!
作者留言

PDF版免费提供倘若有需要,想拿我写的博客进行学习和交流,可以私信我将免费提供PDF版。
留下你的建议倘若你发现本文中的内容和配图有任何错误或改进建议,请直接评论或者私信。
倡导提问与交流关于本文任何不明之处,请及时评论和私信,看到即回复。


参考目录

  • 1.前言
  • 2.题目介绍
  • 3.题解思路
  • 4.代码示例
  • 5.时间/空间复杂度分析


1.前言

今天来分享一道比较中规中矩的题目题解,即电话号码的组合。这道题思路上来说很简单,但是前提得理解深度优先遍历


什么是深度优先遍历?
在这里插入图片描述

举个例子,二叉树的中序遍历(当然二叉树的前序、后序遍历也属于深度优先遍历),按照左子树、根、右子树的方式依次遍历整棵树。

在这里插入图片描述


2.题目介绍

题目链接:LINK
在这里插入图片描述
这道题题意很简单,给到我们一个字符串,然后字符串里有一些数字字符,每个数字字符对应一个特定的字母字符串,挨个取字母字符串元素,取出所有组合即可。

比如,给到我们的数字字符串是:“234”,那我们的遍历图解如下:
在这里插入图片描述

3.题解思路

我们的整体思路使用哈希表存储每个字符数字对应的所有可能的字母,并对其进行回溯。

回溯的过程:我们用一个string类型来维护我们每次维护的字符串结果,得到每个string结果之后,将其尾插到返回结果中去。
该字符串初始为空,每次取电话号码中的一位数字,然后根据这个数字获得该数字对应的所有可能的字母,将其中的一个字母插入到我们维护的string中,然后继续处理电话号码的后一位数字,知道处理完电话号码中的所有数字,即得到一个完整的字母排列。然后进行回退操作,遍历其余的字母排列。

4.代码示例

class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> combinations;//用来返回最后的组合结果if(digits.empty())//如果为空,返回个空vector即可{return combinations;}//下面开始处理一般情况://先制作了哈希表unordered_map<char, string> phoneMap{{'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},{'6', "mno"},{'7', "pqrs"},{'8', "tuv"},{'9', "wxyz"}};string combination;//用来存储每个组合,即一个字符串backtrack(combinations, combination, digits, phoneMap, 0);//返回return combinations;}void backtrack(vector<string>& combinations, string& combination, const string& digits, const unordered_map<char, string>&phoneMap, int index){//当下标取到digit末尾时候,表示完成了一个string制作,要把它加入到combinations中去if(index == digits.size()){combinations.push_back(combination);}else//如果不是,那我们先取digits中的数字,再根据数字拿到对应的string,再取string中所需要的那一位{char digit = digits.at(index);const string& letters = phoneMap.at(digit);for(auto& letter : letters){combination.push_back(letter);backtrack(combinations, combination, digits, phoneMap, index+1);combination.pop_back();}}}
};

5.时间/空间复杂度分析

注意:m指的是给定的一串数字中对应3位字母的数字的个数,n指得是一串数字中对应4位字母得数字得个数。

时间复杂度:O(3^m + 4^n)
时间复杂度主要就是取决于数字长度了,假定每个数字都对应3个字母,那么就是数字个数的三次方,但是存在部分数字是对应四个字母的,所以应该是上面所示。
空间复杂度:O(m + n)
空间复杂度主要取决于两部分,一部分是哈希表,另一部分是我们调用得递归函数所对应的空间开销。其中由于哈希表底层实现,哈希表的空间复杂度为O(1),调用的递归函数最大递归层级就是给定的字符串数字的长度次。



好的,如果本篇文章对你有帮助,不妨点个赞~谢谢。

在这里插入图片描述


EOF

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395697.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

立即升级你的前端技能!跟随这份Vue3项目搭建教程,从零基础到专业,一步步掌握最新Web开发技术,打造响应快速、界面优雅的现代网站。

全能开发套餐&#xff0c;轻松打造现代网站&#xff01;Vue3携手Vite带来开发新体验&#xff0c;结合Axios、Pinia、Element Plus实现功能与美观并重&#xff0c;TailwindCSS与DaisyUI提供设计灵活性&#xff0c;Router 4处理页面导航。从前端到后端&#xff0c;一站式解决&…

一、Matlab基础

文章目录 一、Matlab界面二、Matlab窗口常用命令三、Matlab的数据类型3.1 数值类型3.2 字符和字符串3.3 逻辑类型3.4 函数句柄3.5 结构类型3.6 细胞数组 四、Matlab的运算符4.1 算术运算符4.2 关系运算符4.3 逻辑运算4.4 运算符优先级 五、Matlab的矩阵5.1 矩阵的建立5.2 矩阵的…

【Linux】输入输出重定向

目录 一、概念 二、重定向的本质 三、系统调用接口dup和dup2 3.1 dup 3.2 dup2 一、概念 在之前对Linux的学习中&#xff0c;我们有接触过一系列的重定向命令&#xff0c;例如 >、>>等 它们可以将一个命令的输出或输入重定向到其他地方&#xff0c;如echo命令…

开源应用:AI监测如何成为社会安全的智能盾牌

社会背景 随着社会的快速发展&#xff0c;社会安全管理正站在一个新时代的门槛上。社会对安全管理的需求不断增长&#xff0c;传统的安全措施已难以满足现代社会的需求。AI技术以其独特的数据处理和模式识别能力&#xff0c;正在成为我们社会安全的智能盾牌。 AI大模型识别功能…

3.js - 物理引擎终极

import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls import gsap from gsap // 导入动画库 import * as dat from dat.gui // 导入dat.gui// 导入 cannon-es 引擎 import * as CANNON from cannon-es// -----------------…

探索GPT-4o mini:开启AI驱动的开发新时代

文章目录 GPT-4o mini&#xff1a;小身材&#xff0c;大能量成本与效能的完美平衡 AI辅助开发&#xff1a;从构想到现实自动化文档编写智能代码审查 提升创新能力&#xff1a;AI驱动的新常态模型驱动的设计思维 社区共享与合作知识共享的重要性 未来展望&#xff1a;AI与人类的…

<数据集>agv仓储机器人识别数据集<目标检测>

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;1514张 标注数量(xml文件个数)&#xff1a;1514 标注数量(txt文件个数)&#xff1a;1514 标注类别数&#xff1a;3 标注类别名称&#xff1a;[G1PB2000_Paleteira_AGVS BYD, G1RB5000, AGV-P] 序号类别名称图片数…

6自由度机械手DH坐标系建立

一、建立机械臂DH坐标系 Z为转动关节的转轴&#xff0c;Xi垂直于关节轴i和i1所在的平面&#xff0c;则根据上述方法可以建立坐标系如下图&#xff1a; 二、DH参数表 DH参数设定&#xff1a;机器人的每个连杆可以用4个运动学参数表示&#xff0c;DH法建立坐标系&#xff0c;xi-…

[开端]如何看待“低代码”开发平台的兴起

如何看待“低代码”开发平台的兴起&#xff1f; 近年来&#xff0c;“低代码”开发平台如雨后春笋般涌现&#xff0c;承诺让非专业人士也能快速构建应用程序。这种新兴技术正在挑战传统软件开发模式&#xff0c;引发了IT行业的广泛讨论。低代码平台是提高效率的利器&#xff0…

[开端]JAVA抽象类使用到redis观察着

一、绪论 当redis内容发生变化时需要通知一些观察者做一些动作怎么做&#xff1f; 二、JAVA抽象类 public abstract class AbstractRedisChangeListener {public abstract void change(String key, String value, String crudType); }使用abstract进行修饰一个类 其中抽象类…

SpringBoot中如何自定义自己的过滤器Filter(简易版)

本文不再说SpringMVC中的写法&#xff0c;毕竟现在项目都是SpringBoot&#xff0c;我们还是尽量使用SpringBoot的写法&#xff0c;首先了解一下Filter。 说白了&#xff0c;就是在请求到达服务器之前进行拦截&#xff0c;一般使用场景是拦截登录进行权限校验&#xff0c;当然一…

安装python+python的基础语法

安装python python2为内置&#xff0c;安装python3----3.6.8 最新安装3.12使用源码安装 1.查看yum源&#xff0c;epel [rootpython01 ~]# yum list installed |grep epel 2.安装python3 [rootpython01 ~]# yum -y install python3 3.查看版本 [rootpython01 ~]# python…

Android Studio Gradle多渠道打包

原理使用Android Studio打一次渠道包&#xff0c;用反编译工具反编译后&#xff0c;修改渠道信息重新编译 准备文件 分渠道配置文件&#xff1a;channel.txt ↓ # 多渠道配置里“统计平台”、“市场名称”、“渠道编号”分别代表什么意思&#xff1f; # 统计平台&#xff1a;…

AT32F421驱动BLDC 配合上位机控制与调参

AT32F421驱动BLDC 配合上位机控制与调参 &#x1f527;AT32 电机控制与调参上位机软件&#xff1a;ArteryMotorMonitor&#xff1a;https://www.arterytek.com/cn/support/motor_control.jsp?index0&#x1f33f;测试电机参数&#xff1a;2204-12N14P&#xff0c;无感BLDC&…

LVS(Linux Virtual Server)

简介 LVS&#xff08;Linux Virtual Server&#xff09;是一个高性能的开源负载均衡解决方案&#xff0c;它通过在Linux内核中实现IPVS&#xff08;IP Virtual Server&#xff09;模块来提供负载均衡功能。LVS能够将外部请求根据特定的算法分发到后端的多个服务器上&#xff0c…

百度文心一言API调用,千帆大模型获取API Key和API Secret图解

百度文心一言大模型调用教程&#xff0c;获取文心一言API Key和API Secret的方法&#xff0c;码笔记mabiji.com告诉大家在百度智能云的千帆大模型平台创建应用&#xff0c;即可获取文心一言的API Key和API Secret&#xff0c;详细流程如下&#xff1a; 1、在百度智能云的千帆大…

gitlab项目添加新成员

gitlab项目添加新成员 1、进入项目&#xff0c;找到settings----->点击Members 2、手动输入要添加成员的账号或者搜索&#xff0c;最后点击Add to project就可以了 choose a role permission 是为要添加的成员选择角色权限 补充&#xff1a; ‌Maintainer&#xff1a;拥…

同态加密和SEAL库的介绍(八)性能

本篇会对比三种加密方案&#xff0c;同时每种方案配置三种参数。即九种情况下的各个操作的性能差异&#xff0c;为大家选择合适的方案和合适的参数提供参考。表格中所有时长的单位均为微妙&#xff0c;即 。 当然数据量比较大&#xff0c;为了方便大家查找&#xff0c…

[BSidesCF 2019]Kookie1

打开题目&#xff0c;看到 根据提示&#xff0c;账号&#xff1a;cookie。密码&#xff1a;monster。试一下登录&#xff0c;登陆成功 抓包看看信息 根据提示&#xff0c; 看一下返回包 账号要加username要改成admin&#xff0c;改一下试试 构造cookie 直接得到flag flag{c…

Redis远程字典服务器(3)——常用数据结构和单线程模型

目录 一&#xff0c;常用数据结构 1.0 前言 1.1 string 1.2 hash 1.3 list 1.4 set 1.5 zset 1.6 演示 二&#xff0c;关于单线程模型 2.1 关于Redis的单线程 2.2 Redis为什么快 一&#xff0c;常用数据结构 1.0 前言 Redis是采用键值对的方式来存储数据的&#…