【面试经典 150 | 回溯】电话号码的字母组合

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 解题思路
    • 方法一:回溯
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【字符串】【回溯】


题目来源

17. 电话号码的字母组合


解题思路

方法一:回溯

思路

给定一个仅包含数字 2-9 的字符,现在需要返回它能表示的字母组合。每个数字会和几个字符形成映射,因此需要先使用一个哈希表建立映射关系。

建立好哈希表之后,利用「回溯」枚举出所有可能的字母组合。所谓的「回溯」指的是从问题的某一状态出发沿着某一分支前进,当这条分支走到尽头时,回退一步,从另一种可能的状态出发,如此往复,直至走完所有的路径。

对于示例 1 就是从数字字符的第一个字符 ‘2’ 出发,‘2’ 在哈希表中对应三个字符 ,我们选择一个字符作为分支出发,比如字符 ‘a’;继续出发遇到第二个数字字符 ‘3’,‘3’ 在哈希表中也对应三个字符 ,比如我们选择字符 ‘d’ 出发,这时走到路径尽头了;于是回退一步从 ‘3’ 在哈希表中对应的三个字符出选出另一个字符…如此便可以得到 “ad”、“ae”、“af” 三个字符。这时候再回退一步从 ‘2’ 在哈希表中对应的三个字符出选出另一个字符,如此就能依次得到字符 “bd”, “be”, “bf”, “cd”, “ce”, “cf”。

代码

class Solution {
private:
    unordered_map<char, string> num2Alpha = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };    
    vector<string> ret;
    string str;
    
    void dfs(string digits, int idex){
        if(idex == digits.size()){
            ret.push_back(str);
            return;
        }

        string alpha = num2Alpha[digits[idex]];
        for(auto &c : alpha){
            str.push_back(c);
            dfs(digits, idex+1);
            str.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            return ret;
        }
        
        dfs(digits, 0);
        return ret;
    }
};

复杂度分析

时间复杂度: O ( 3 m × 4 m ) O(3^m \times 4^m) O(3m×4m),其中 m m m 是输入中对应 3 个字母的数字个数(包括数字 2、3、4、5、6、8), n n n 是输入中对应 4 个字母的数字个数(包括数字 7、9)。当输入包含 m m m 个对应 3 个字母的数字和 n n n 个对应 4 个字母的数字时,不同的字母组合一共有 3 m × 4 n 3^m \times 4^n 3m×4n 种,需要遍历每一种字母组合。

空间复杂度: O ( m + n ) O(m+n) O(m+n)。空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数,哈希表的大小与输入无关,可以看成常数,递归调用层数最大为 m + n m+n m+n


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

IOTE2024第二十一届(上海)国际物联网展览会4月24日-26日开幕

交流产业信息&#xff0c;把脉发展方向&#xff0c;IOTE 国际物联网展是每年物联网行业、企业、用户交流合作的大型平台。2024年4月24-26日IOTE2024第二十一届国际物联网展•上海站&#xff0c;在上海世博展览馆开展。 本次物联网展汇聚全球超300家参展企业、3万来自工业、物流…

区块链技术与应用学习笔记(1-4节)——北大肖臻课程

目录 1. 区块链初识(课程简介&#xff09; 被过度炒作&#xff0c;落地应用有限&#xff1f; 下一代的价值互联网&#xff1f;世界上最慢的数据库&#xff1f; 2. BTC-密码学原理&#xff08;比特币&#xff09; 1)哈希 哈希函数特点 个人学习所得 2)签名 个人对于…

工业测径仪的应用场景和可靠性判断

关键字:线缆测径仪,圆棒测径仪,圆管测径仪,金属棒管测径仪,工业测径仪,智能测径仪 智能测径仪主要应用于以下领域&#xff1a; 金属加工&#xff1a;测量金属线材、棒材、管材等的直径。线缆制造&#xff1a;检测电线、电缆的直径。塑料管材生产&#xff1a;监控塑料管材的外…

Python 数组控件的使用

当一个UI窗口界面内有多个相同类型的控件&#xff0c;且这多个控件的功能都类似时&#xff0c;使用数组控件是一个非常不错的选择&#xff0c;可以大大减少代码的编写 且 代码易读性强&#xff0c;可惜的是Python好象是没有数组控件这个东东。 我们来看看以下一个界面&#xff…

前端CSS基础11(相对定位,绝对定位,固定定位,粘性定位)

前端CSS基础11&#xff08;相对定位&#xff0c;绝对定位&#xff0c;固定定位&#xff0c;粘性定位&#xff09; CSS相对定位&#xff08;position: relative;&#xff09;相对定位的参考点在哪&#xff1f; CSS绝对定位&#xff08;position: absolute&#xff09;如何设置绝…

微信小程序:6.事件

什么事事件 事件就是渲染层到逻辑层的通讯方式&#xff0c;比如提交表单&#xff0c;按钮点击都可以看作一个事件。 小程序中常用的事件 事件对象属性列表 当事件回调时&#xff0c;会收到一个事件对象event&#xff0c;他详细属性如夏表所示&#xff1a; target和curren…

yudao-cloud微服务系统系统模块+后台管理系统成功运行

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 系列文章目录 第一章 芋…

【软件测试】终于有人讲明白:bug的分类和定级了!

01、bug的定义 一般是指不满足用户需求的则可以认为是bug&#xff0c;狭义指软件程序的漏洞或缺陷&#xff0c;广义指测试工程师或用户提出的软件可改进的细节、或与需求文档存在差异的功能实现等 对应三个测试目的&#xff1a; 为了发现程序的代码或业务逻辑错误 为了检查产…

《第二行代码》第二版学习笔记(6)——内容提供器

文章目录 一 运行时权限2.权限分类3 运行时申请权限 二、内容提供器1、 ContentResolver的基本用法2、现有的内容提供器3、创建自己的内容提供器2.1 创建内容提供器的步骤2.2 跨程序数据共享 内容提供器&#xff08;Content Provider&#xff09;主要用于在不同的应用程序之间实…

2024年大数据应用、智能控制与软件工程国际会议(BDAICSE2024)

2024年大数据应用、智能控制与软件工程国际会议(BDAICSE2024) 会议简介 我们诚挚邀请您参加2024年大数据应用、智能控制和软件工程国际会议&#xff08;BDAICSE2024&#xff09;。这次会议将在美丽的长沙市举行。 本次大会旨在汇聚全球大数据应用、智能控制、软件工程等领…

WebGIS

文章目录 GIS的全名是Geographic Information System&#xff0c;中文全名是地理信息系统。 它是在计算机硬、软件系统支持下&#xff0c;对整个或部分地球表层&#xff08;包括大气层&#xff09;空间中的有关地理分布数据进行采集、储存、管理、运算、分析、显示和描述的技术…

Windows搭建php文件管理服务Tiny File Manager并发布至公网可访问

文章目录 1. 前言2.Tiny File Manager网站搭建2.1.Tiny file manager下载和安装2.2 Tiny file manager网页测试2.3 内网穿透工具下载安装 3. 本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试总结 1. 前言 今天&#xff0c;笔者就为大家介绍一款只有两个文件…

大数据第七天

文章目录 吐槽一下这个是怎么需要真的这么大吗? 内核错误内核软死锁&#xff08;soft lockup&#xff09;我这个cpu很高吗?大模型都说了不超过80就行了 FinBi安装FinBI下载链接安装时间比较长 吐槽一下 dbeaver 查询hive 数据信息是真的慢&#xff0c;没有一点快的方式&…

鲁棒控制理论学习:静态状态反馈H∞控制器

鲁棒性&#xff0c;即系统的健壮性&#xff0c;是指在异常和危险情况下系统能够维持其功能和性能的能力。在控制系统中&#xff0c;鲁棒性表现为系统在参数摄动下维持某些性能的特性。例如&#xff0c;当控制系统面临输入错误、磁盘故障、网络过载或有意攻击等挑战时&#xff0…

dist包在windows的nginx下部署运行

nginx 附带下载包 我用夸克网盘分享了「nginx-1.18.0.zip」 链接&#xff1a;https://pan.quark.cn/s/e87bbf87a742 将dist放到html文件目录下 3.找到nginx的配置文件&#xff0c;conf 下&#xff0c;用编辑器打开 nginx.conf 编辑。 location ^~/api {rewrite ^/api/(.*)…

python--使用pika库操作rabbitmq实现需求

Author: wencoo Blog&#xff1a;https://wencoo.blog.csdn.net/ Date: 22/04/2024 Email: jianwen056aliyun.com Wechat&#xff1a;wencoo824 QQ&#xff1a;1419440391 Details:文章目录 目录正文 或 背景pika链接mqpika指定消费数量pika自动消费实现pika获取队列任务数量pi…

小型内衣裤洗衣机哪个牌子好?六大选购锦囊私藏分享

内衣洗衣机是现代家庭必不可少的小家电&#xff0c;它不仅方便快捷&#xff0c;还能够保持衣物清洁和卫生。然而&#xff0c;市场上洗衣机品牌众多&#xff0c;质量和性能参差不齐&#xff0c;使得消费者购买时难以做出选择。那么&#xff0c;小型内衣裤洗衣机哪个牌子好&#…

【java9】java9新特性之增强@Deprecated注解

一个使用Deprecated注解的元素&#xff0c;无论是一个类或是一个方法&#xff0c;可能是由以下原因导致了不应该再使用它&#xff1a; 使用它可能会导致错误&#xff1b;在未来的版本中不被兼容&#xff1b;在未来的版本中可能会被删除&#xff1b;存在更好的更有效的替代方法…

机械臂过程

rosdep install --from-paths src --ignore-src --rosdistro melodic0、安装机械手臂 官方教程&#xff1a; 前人教程&#xff1a;UR5机械臂仿真实例 rosdep update 出错&#xff0c;使用小鱼的大佬的 一键配置 wget http://fishros.com/install -O fishros && . fish…

软件测试报告的用途

软件测试报告的用途十分广泛&#xff0c;主要体现在以下几个方面&#xff1a; 评估软件质量&#xff1a;软件测试报告是对软件进行全面、系统测试后的总结&#xff0c;通过报告中的各项数据和结果&#xff0c;可以评估软件的质量水平&#xff0c;包括功能的完整性、性能的稳定…