【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’] 的一个数字。
思路:
数字和字母如何映射
首先要解决的问题是数字和字母如何映射,可以使用map或者定义一个二维数组,例如:string letterMap[10],来做映射,这里定义一个二维数组,代码如下:
// 数字和字母映射
const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9
};
回溯法来解决n个for循环的问题
例如:输入:“23”,抽象为树形结构,如图所示:
图中可以看出遍历的深度,就是输入"23"的长度,而叶子节点就是我们要收集的结果,输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
回溯三部曲:
- 确定回溯函数参数
首先需要一个字符串path来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。
再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。
注意这个index可不是77.组合 中等中的startIndex了。
这个index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。
代码如下:
vector<string> result;
string path;
void backtracking(const string& digits, int index)
- 确定终止条件
例如输入用例"23",两个数字,那么根节点往下递归两层就可以了,叶子节点就是要收集的结果集。
那么终止条件就是如果index 等于 输入的数字个数(digits.size)了(本来index就是用来遍历digits的)。
然后收集结果,结束本层递归。
代码如下:
if (index == digits.size()) {result.push_back(s);return;
}
- 确定单层遍历逻辑
首先要取index指向的数字,并找到对应的字符集(手机键盘的字符集)。
然后for循环来处理这个字符集,代码如下:
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for(int i = 0; i < letters.size(); i++){path.push_back(letters[i]); // 处理backtracking(digits, index + 1); // 递归path.pop_back(); // 回溯
}
注意这里for循环,可不像是在回溯算法:求组合问题77.组合 中等中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而77.组合 中等是求同一个集合中的组合!
代码:
class Solution {
public:// 数字和字母映射const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz" // 9};vector<string> result;string path;// charMap为当前数字对应的字母字符串void backtracking(const string& digits, int index){if(digits.size() == 0) return;if(index == digits.size()){result.push_back(path);return;}int digit = digits[index] - '0'; // 将index指向的数字转为intstring letters = letterMap[digit]; // 取数字对应的字符集for(int i = 0; i < letters.size(); i++){path.push_back(letters[i]); // 处理backtracking(digits, index + 1); // 递归path.pop_back(); // 回溯}}vector<string> letterCombinations(string digits) {backtracking(digits, 0);return result;}
};
总结:
时间复杂度: O(3^m * 4^n),其中 m 是对应三个字母的数字个数,n 是对应四个字母的数字个数
空间复杂度: O(3^m * 4^n)
本并重点强调了和前面讲解过的77.组合 中等的区别,本题是多个集合求组合,所以在回溯的搜索过程中,都有一些细节需要注意的。
参考:
代码随想录
相关文章:

【17. 电话号码的字母组合 中等】
题目: 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 输入:digits “23”…...

数据结构初阶---排序
一、排序相关概念与运用 1.排序相关概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的…...

【从0-1实现一个前端脚手架】
目录 介绍为什么需要脚手架?一个脚手架应该具备哪些功能? 脚手架实现初始化项目相关依赖实现脚手架 发布 介绍 为什么需要脚手架? 脚手架本质就是一个工具,作用是能够让使用者专注于写代码,它可以让我们只用一个命令…...

AI文章管理系统(自动生成图文分发到分站)
最近帮一个网上的朋友做了一套AI文章生成系统。他的需求是这样: 1、做一个服务端转接百度文心一言的生成文章的API接口。 2、服务端能注册用户,用户在服务端注册充值后可以获取一个令牌,这个令牌填写到客户端,客户端就可以根据客…...
【Leetcode 每日一题】3270. 求出数字答案
问题背景 给你三个 正 整数 n u m 1 num_1 num1, n u m 2 num_2 num2 和 n u m 3 num_3 num3。 数字 n u m 1 num_1 num1, n u m 2 num_2 num2 和 n u m 3 num_3 num3 的数字答案 k e y key key 是一个四位数,定义如下&…...

基于单片机的无线气象仪系统设计(论文+源码)
1系统方案设计 如图2.1所示为无线气象仪系统设计框架。系统设计采用STM32单片机作为主控制器,结合DHT11温湿度传感器、光敏传感器、BMP180气压传感器、PR-3000-FS-N01风速传感器实现气象环境的温度、湿度、光照、气压、风速等环境数据的检测,并通过OLED1…...
【数据库】Mysql精简回顾复习
一、概念 数据库(DB):数据存储的仓库数据库管理系统(DBMS):操纵和管理数据库的大型软件SQL:操作关系型数据库的编程语言,是一套标准关系型数据库(RDBMS)&…...
深入理解 HTTP 的 GET、POST 方法与 Request 和 Response
HTTP 协议是构建 Web 应用的基石,GET 和 POST 是其中最常用的请求方法。无论是前端开发、后端开发,还是接口测试,对它们的深入理解都显得尤为重要。在本文中,我们将介绍 GET 和 POST 方法,以及 Request 和 Response 的…...
MySQL 中联合索引相比单索引性能提升在哪?
首先我们要清楚所以也是要占用磁盘空间的,随着表中数据量越来越多,索引的空间也是随之提升的,因而单表不建议定义过多的索引,所以使用联合索引可以在一定程度上可以减少索引的空间占用其次,使用联合索引的情况下&#…...

第34天:安全开发-JavaEE应用反射机制攻击链类对象成员变量方法构造方法
时间轴: Java反射相关类图解: 反射: 1、什么是 Java 反射 参考: https://xz.aliyun.com/t/9117 Java 提供了一套反射 API ,该 API 由 Class 类与 java.lang.reflect 类库组成。 该类库包含了 Field 、 Me…...

C++笔记之数据单位与C语言变量类型和范围
C++笔记之数据单位与C语言变量类型和范围 code review! 文章目录 C++笔记之数据单位与C语言变量类型和范围一、数据单位1. 数据单位表:按单位的递增顺序排列2. 关于换算关系的说明3. 一般用法及注意事项4. 扩展内容5. 理解和使用建议二、C 语言变量类型和范围基本数据类型标准…...
算法-拆分数位后四位数字的最小和
力扣题目2160. 拆分数位后四位数字的最小和 - 力扣(LeetCode) 给你一个四位 正 整数 num 。请你使用 num 中的 数位 ,将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ,且 num 中 所有 数位都必须使用。 …...
Python 管理 GitHub Secrets 和 Workflows
在现代软件开发中,自动化配置管理变得越来越重要。本文将介绍如何使用 Python 脚本来管理 GitHub 仓库的 Secrets 和 Workflows,这对于需要频繁更新配置或管理多个仓库的团队来说尤为有用。我们将分三个部分进行讨论:设置 GitHub 权限、创建 GitHub Secret 和创建 GitHub Wo…...

指令的修饰符
指令的修饰符 参考文献: Vue的快速上手 Vue指令上 Vue指令下 Vue指令的综合案例 文章目录 指令的修饰符指令修饰符 结语 博客主页: He guolin-CSDN博客 关注我一起学习,一起进步,一起探索编程的无限可能吧!让我们一起努力&…...
C# 正则表达式完全指南
C# 正则表达式完全指南 C#通过 System.Text.RegularExpressions 命名空间提供强大的正则表达式支持。本指南将详细介绍C#中正则表达式的使用方法、性能优化和最佳实践。 1. 基础知识 1.1 命名空间导入 using System.Text.RegularExpressions;1.2 基本使用 public class Re…...
【笔记整理】记录参加骁龙AIPC开发者技术沙龙的笔记
AIoT 首先了解了一个概念叫AIoT,我的理解就是AI IoT 5G,通过AI的发展使得边缘计算、数据整合和处理变得快捷方便,不仅限于传统的云端数据处理,在边缘的IoT设备上也可以进行智能化打造,通过5G的通信能力扩展可以实现…...

论文解析 | 基于语言模型的自主代理调查
论文 《A Survey on Large Language Model-based Autonomous Agents》 对基于大型语言模型(LLM)的自主智能体(Autonomous Agents)进行了全面调查。随着大型语言模型(如 GPT 系列、BERT、T5 等)的快速发展&a…...
面试加分项:Android Framework AMS 全面概述和知识要点
第一章:AMS 的架构与组件 1.1 AMS 整体架构 在 Android 系统的庞大体系中,AMS(Activity Manager Service)就如同一个中枢神经系统,是整个系统的核心服务之一,对应用的性能和用户体验有着直接且关键的影响 。它的整体架构由 Client 端和 Service 端两大部分组成,这两端相…...

EasyCVR视频汇聚平台如何配置webrtc播放地址?
EasyCVR安防监控视频系统采用先进的网络传输技术,支持高清视频的接入和传输,能够满足大规模、高并发的远程监控需求。平台支持多协议接入,能将接入到视频流转码为多格式进行分发,包括RTMP、RTSP、HTTP-FLV、WebSocket-FLV、HLS、W…...
用户界面软件04
后果 使用这种架构很容易对两个层面的非功能性需求进行优化,但是你仍然需要小心不要将功能 需求重复实现。 现在,两个层面可能有完全不同的设计。比如,用户界面层可能使用配件模型(Widget Model), 以大量的…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...

九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...