当前位置: 首页 > news >正文

【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”,抽象为树形结构,如图所示:

17. 电话号码的字母组合

图中可以看出遍历的深度,就是输入"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. 电话号码的字母组合 中等】

题目&#xff1a; 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits “23”…...

数据结构初阶---排序

一、排序相关概念与运用 1.排序相关概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的…...

【从0-1实现一个前端脚手架】

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

AI文章管理系统(自动生成图文分发到分站)

最近帮一个网上的朋友做了一套AI文章生成系统。他的需求是这样&#xff1a; 1、做一个服务端转接百度文心一言的生成文章的API接口。 2、服务端能注册用户&#xff0c;用户在服务端注册充值后可以获取一个令牌&#xff0c;这个令牌填写到客户端&#xff0c;客户端就可以根据客…...

【Leetcode 每日一题】3270. 求出数字答案

问题背景 给你三个 正 整数 n u m 1 num_1 num1​&#xff0c; n u m 2 num_2 num2​ 和 n u m 3 num_3 num3​。 数字 n u m 1 num_1 num1​&#xff0c; n u m 2 num_2 num2​ 和 n u m 3 num_3 num3​ 的数字答案 k e y key key 是一个四位数&#xff0c;定义如下&…...

基于单片机的无线气象仪系统设计(论文+源码)

1系统方案设计 如图2.1所示为无线气象仪系统设计框架。系统设计采用STM32单片机作为主控制器&#xff0c;结合DHT11温湿度传感器、光敏传感器、BMP180气压传感器、PR-3000-FS-N01风速传感器实现气象环境的温度、湿度、光照、气压、风速等环境数据的检测&#xff0c;并通过OLED1…...

【数据库】Mysql精简回顾复习

一、概念 数据库&#xff08;DB&#xff09;&#xff1a;数据存储的仓库数据库管理系统&#xff08;DBMS&#xff09;&#xff1a;操纵和管理数据库的大型软件SQL&#xff1a;操作关系型数据库的编程语言&#xff0c;是一套标准关系型数据库&#xff08;RDBMS&#xff09;&…...

深入理解 HTTP 的 GET、POST 方法与 Request 和 Response

HTTP 协议是构建 Web 应用的基石&#xff0c;GET 和 POST 是其中最常用的请求方法。无论是前端开发、后端开发&#xff0c;还是接口测试&#xff0c;对它们的深入理解都显得尤为重要。在本文中&#xff0c;我们将介绍 GET 和 POST 方法&#xff0c;以及 Request 和 Response 的…...

MySQL 中联合索引相比单索引性能提升在哪?

首先我们要清楚所以也是要占用磁盘空间的&#xff0c;随着表中数据量越来越多&#xff0c;索引的空间也是随之提升的&#xff0c;因而单表不建议定义过多的索引&#xff0c;所以使用联合索引可以在一定程度上可以减少索引的空间占用其次&#xff0c;使用联合索引的情况下&#…...

第34天:安全开发-JavaEE应用反射机制攻击链类对象成员变量方法构造方法

时间轴&#xff1a; Java反射相关类图解&#xff1a; 反射&#xff1a; 1、什么是 Java 反射 参考&#xff1a; https://xz.aliyun.com/t/9117 Java 提供了一套反射 API &#xff0c;该 API 由 Class 类与 java.lang.reflect 类库组成。 该类库包含了 Field 、 Me…...

C++笔记之数据单位与C语言变量类型和范围

C++笔记之数据单位与C语言变量类型和范围 code review! 文章目录 C++笔记之数据单位与C语言变量类型和范围一、数据单位1. 数据单位表:按单位的递增顺序排列2. 关于换算关系的说明3. 一般用法及注意事项4. 扩展内容5. 理解和使用建议二、C 语言变量类型和范围基本数据类型标准…...

算法-拆分数位后四位数字的最小和

力扣题目2160. 拆分数位后四位数字的最小和 - 力扣&#xff08;LeetCode&#xff09; 给你一个四位 正 整数 num 。请你使用 num 中的 数位 &#xff0c;将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 &#xff0c;且 num 中 所有 数位都必须使用。 …...

Python 管理 GitHub Secrets 和 Workflows

在现代软件开发中,自动化配置管理变得越来越重要。本文将介绍如何使用 Python 脚本来管理 GitHub 仓库的 Secrets 和 Workflows,这对于需要频繁更新配置或管理多个仓库的团队来说尤为有用。我们将分三个部分进行讨论:设置 GitHub 权限、创建 GitHub Secret 和创建 GitHub Wo…...

指令的修饰符

指令的修饰符 参考文献&#xff1a; Vue的快速上手 Vue指令上 Vue指令下 Vue指令的综合案例 文章目录 指令的修饰符指令修饰符 结语 博客主页: He guolin-CSDN博客 关注我一起学习&#xff0c;一起进步&#xff0c;一起探索编程的无限可能吧&#xff01;让我们一起努力&…...

C# 正则表达式完全指南

C# 正则表达式完全指南 C#通过 System.Text.RegularExpressions 命名空间提供强大的正则表达式支持。本指南将详细介绍C#中正则表达式的使用方法、性能优化和最佳实践。 1. 基础知识 1.1 命名空间导入 using System.Text.RegularExpressions;1.2 基本使用 public class Re…...

【笔记整理】记录参加骁龙AIPC开发者技术沙龙的笔记

AIoT 首先了解了一个概念叫AIoT&#xff0c;我的理解就是AI IoT 5G&#xff0c;通过AI的发展使得边缘计算、数据整合和处理变得快捷方便&#xff0c;不仅限于传统的云端数据处理&#xff0c;在边缘的IoT设备上也可以进行智能化打造&#xff0c;通过5G的通信能力扩展可以实现…...

论文解析 | 基于语言模型的自主代理调查

论文 《A Survey on Large Language Model-based Autonomous Agents》 对基于大型语言模型&#xff08;LLM&#xff09;的自主智能体&#xff08;Autonomous Agents&#xff09;进行了全面调查。随着大型语言模型&#xff08;如 GPT 系列、BERT、T5 等&#xff09;的快速发展&a…...

面试加分项:Android Framework AMS 全面概述和知识要点

第一章:AMS 的架构与组件 1.1 AMS 整体架构 在 Android 系统的庞大体系中,AMS(Activity Manager Service)就如同一个中枢神经系统,是整个系统的核心服务之一,对应用的性能和用户体验有着直接且关键的影响 。它的整体架构由 Client 端和 Service 端两大部分组成,这两端相…...

EasyCVR视频汇聚平台如何配置webrtc播放地址?

EasyCVR安防监控视频系统采用先进的网络传输技术&#xff0c;支持高清视频的接入和传输&#xff0c;能够满足大规模、高并发的远程监控需求。平台支持多协议接入&#xff0c;能将接入到视频流转码为多格式进行分发&#xff0c;包括RTMP、RTSP、HTTP-FLV、WebSocket-FLV、HLS、W…...

用户界面软件04

后果 使用这种架构很容易对两个层面的非功能性需求进行优化&#xff0c;但是你仍然需要小心不要将功能 需求重复实现。 现在&#xff0c;两个层面可能有完全不同的设计。比如&#xff0c;用户界面层可能使用配件模型&#xff08;Widget Model&#xff09;&#xff0c; 以大量的…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

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

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

LLMs 系列实操科普(1)

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

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; 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类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...