LeetCode刷题--- 字母大小写全排列

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 http://t.csdnimg.cn/yUl2I   

【C++】    

 http://t.csdnimg.cn/6AbpV 

数据结构与算法

 http://t.csdnimg.cn/hKh2l


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


字母大小写全排列

题目链接:字母大小写全排列

题目

给定一个字符串 s ,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。

返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。

示例 1:

输入:s = "a1b2"
输出:["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

输入: s = "3z4"
输出: ["3z4","3Z4"]

提示:

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成

解法

题目解析

  • 题目的意思非常简单,给定一个字符串 s 
  • 通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。
  • 返回 所有可能得到的字符串集合 ,以 任意顺序 返回输出。

示例 1:

输入:s = "a1b2"
输出:["a1b2", "a1B2", "A1b2", "A1B2"]

算法原理思路讲解 

只需要对英⽂字⺟进⾏处理,处理每个元素时存在三种情况
  1. 不进⾏处理;
  2. 若当前字⺟是英⽂字⺟并且是⼤写,将其修改为⼩写;
  3. 若当前字⺟是英⽂字⺟并且是⼩写,将其修改为⼤写。

一、画出决策树

决策树就是我们后面设计函数的思路


二、设计代码

(1)全局变量

   string path;vector<string> ret;
  • ret(存储转变大小写,获得一个个新的字符串)
  • path(组合的路径记录)

(2)设计递归函数

void dfs(string s, int pos);  // 表示现在要处理的元素的下标
  • 参数:s(字符串),pos(当前要处理的元素下标);
  • 返回值:无;
  • 函数作用:查找所有可能的字符串集合,并将其记录在答案列表。

从前往后按序进⾏递归,递归流程如下
  1. 递归结束条件:当前需要处理的元素下标越界,表⽰处理完毕,记录当前状态并返回;
  2. 判断当前元素是否为数字,若是,对当前元素不进⾏任何处理,直接递归下⼀位元素;
  3. 判断当前元素是否为⼩写字⺟,若是,将其修改为⼤写字⺟并递归下⼀个元素,递归结束时撤销修改操作;
  4. 判断当前元素是否为⼤写字⺟,若是,将其修改为⼩写字⺟并递归下⼀个元素,递归结束时撤销修改操作;

以上思路讲解完毕,大家可以自己做一下了


代码实现

  • 时间复杂度:O(n×2^{n}),其中 n 表示字符串的长度。递归深度最多为 n,所有可能的递归子状态最多为 2^{n}个,每次个子状态的搜索时间为 O(n),因此时间复杂度为 O(n×2^{n})。
  • 空间复杂度:O(n×2^{n})。递归深度最多为 n,。队列中的元素数目最多为 2^{n} 个,每次个子状态的搜索时间为 O(n),因此空间复杂度为 O(n×2^{n}) 。
class Solution {
public:string path;vector<string> ret;void dfs(string s, int pos)  // 表示现在要处理的元素的下标{if (path.size() == s.size()){ret.push_back(path);return;}if (s[pos] >= '0' && s[pos] <= '9'){path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();}else{if (s[pos] >= 'a' && s[pos] <= 'z'){path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();path.push_back(s[pos]-32);dfs(s, pos + 1);path.pop_back();}else{path.push_back(s[pos]);dfs(s, pos + 1);path.pop_back();path.push_back(s[pos] + 32);dfs(s, pos + 1);path.pop_back();}}}vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}
};

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

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

相关文章

阿里云 ACK 新升级,打造智算时代的现代化应用平台

作者&#xff1a;易立 今天&#xff0c;能想到的或是想不到的领域&#xff0c;对容器和 Kubernetes 的需求都居高不减&#xff0c;使这项技术正在真正走向无处不在。 在 2023 云栖大会上&#xff0c;阿里云云原生产品线容器服务负责人易立关于容器服务 ACK 在本届亚运会上应用…

公众号推荐流量玩法的3个秘密

从微信生态的流量触点来看&#xff0c;公众号链接着私聊、朋友圈、微信群、小程序、视频号、搜一搜、看一看等一切与目标用户能接触到的中转站 流量的尽头是私域。而对于大部分普通人来说&#xff0c;公众号可以作为私域的第一站。且相比个人微信号&#xff0c;其有着深度价值…

【Java】MybatisPlus

MybatisPlus MybatisPlus是在mybatis基础上的一个增强型工具。它对mybatis的一些操作进行了简化&#xff0c;能够提高开发的效率。 springboot整合了mybatis之后&#xff0c;其实已经非常方便了&#xff0c;只需要导入mybatis的包后&#xff0c;在配置文件中编写数据源信息&a…

移动安全APP--Frida+模拟器,模拟器+burp联动

最近测APP被通报了&#xff0c;问题点测得比较深&#xff0c;涉及到frida和burp抓包&#xff0c;一般在公司可能会有网络的限制&#xff0c;手机没办法抓包&#xff0c;我就直接在模拟器上试了&#xff0c;就在这记录一下安装过程。 目录 一、Frida安装 二、burp与逍遥模拟器…

win11下配置visual studio 2022+PCL1.13.1

第一部分&#xff1a;visual studio2022 安装 vs官网网址如下&#xff1a;https://visualstudio.microsoft.com/zh-hans/vs/ 第一步&#xff1a;我们打开官网链接&#xff0c;按如下操作点击下载免费版本的exe文件 第二步&#xff1a;打开下载目录下的安装文件进行安装&#…

【Linux系统基础】(5)在Linux上集群化环境前置准备及部署Zookeeper、Kafka软件详细教程

集群化环境前置准备 介绍 在前面&#xff0c;我们所学习安装的软件&#xff0c;都是以单机模式运行的。 后续&#xff0c;我们将要学习大数据相关的软件部署&#xff0c;所以后续我们所安装的软件服务&#xff0c;大多数都是以集群化&#xff08;多台服务器共同工作&#xf…

DN-DETR调试记录

先前的DN-DETR模型都是在服务器上运行的&#xff0c;后来在本地运行时出现了一些小问题&#xff0c;这篇博文则主要介绍DN-DETR模型在本地运行时所需要做的配置。 运行环境 首先DN-DETR的运行环境与DINO一致&#xff0c;这里就不再赘述了。 博主使用的本地配置是I7-13700H406…

CentOS7部署bitbucket7.21.20-postgresql版

文章目录 1.资源下载2.上传服务器3.赋予执行权限并执行安装4.执行安装5.访问Bitbucket6.Bitbucket安装页面配置6.1连接Jira应用程序到PostgreSQL6.1.1创建并配置PostgreSQL数据库6.1.2测试数据库连接 6.2授权6.2.1授权包6.2.1.1资源地址6.2.1.2上传到服务器 6.2.2停止bitbucket…

Linux ContOS7 日志管理(rsyslog)

目录 01. rsyslog 记录日志程序 02.日志文件 03.日志等级 Linux 日志文件是记录 Linux 系统运行信息的文件。它们类似于人类的日记&#xff0c;记录了系统的各种活动&#xff0c;如用户登录、进程启动、错误消息等。 Linux 日志文件通常存储在 /var/log/ 目录中。该目录包含…

顺序表的实现

目录 一. 数据结构相关概念​ 二、线性表 三、顺序表概念及结构 3.1顺序表一般可以分为&#xff1a; 3.2 接口实现&#xff1a; 四、基本操作实现 4.1顺序表初始化 4.2检查空间&#xff0c;如果满了&#xff0c;进行增容​编辑 4.3顺序表打印 4.4顺序表销毁 4.5顺…

vmware安装中标麒麟高级服务器操作系统 V7.0

vmware安装中标麒麟高级服务器操作系统 V7.0 1、下载中标麒麟高级服务器操作系统 V7.0镜像2、安装中标麒麟高级服务器操作系统 V7.02.1、新建虚拟机2.2、安装虚拟机 3、配置中标麒麟高级服务器操作系统 V7.03.1、登录系统3.2、配置静态IP地址 和 dns3.3、查看磁盘分区3.4、查看…

Java网络爬虫拼接姓氏,名字并写出到txt文件(实现随机取名)

目录 1.爬取百家姓1.爬取代码2.爬取效果 2.爬取名字1.筛选男生名字2.筛选女生名字 3.数据处理&#xff08;去除重复&#xff09;4.拼接数据5.将数据写出到文件中 1.爬取百家姓 目标网站&#xff0c;仅作为实验目的。 ①爬取姓氏网站&#xff1a; https://hanyu.baidu.com/shic…

【OAuth2】授权框架的四种授权方式详解

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《OAuth 2》。&#x1f3af;&#x1f3af; &#x1…

经典文献阅读之--RenderOcc(使用2D标签训练多视图3D Occupancy模型)

0. 简介 3D占据预测在机器人感知和自动驾驶领域具有重要的潜力&#xff0c;它将3D场景量化为带有语义标签的网格单元。最近的研究主要利用3D体素空间中的完整占据标签进行监督。然而&#xff0c;昂贵的注释过程和有时模糊的标签严重限制了3D占据模型的可用性和可扩展性。为了解…

Netty-4-网络编程模式

我们经常听到各种各样的概念——阻塞、非阻塞、同步、异步&#xff0c;这些概念都与我们采用的网络编程模式有关。 例如&#xff0c;如果采用BIO网络编程模式&#xff0c;那么程序就具有阻塞、同步等特质。 诸如此类&#xff0c;不同的网络编程模式具有不同的特点&#xff0c…

​创新驱动,边缘计算领袖:亚马逊云科技海外服务器服务再进化

2022年亚马逊云科技re:Invent盛会于近日在拉斯维加斯成功召开&#xff0c;吸引了众多业界精英和创新者。亚马逊云科技边缘服务副总裁Jan Hofmeyr在演讲中分享了关于亚马逊云科技海外服务器边缘计算的最新发展和创新成果&#xff0c;引发与会者热烈关注。 re:Invent的核心主题是…

VMware虚拟机的安装配置

目录 一. VMware虚拟机的安装 二. VMware配置虚拟机 三. VMware安装windows server 2012 一. VMware虚拟机的安装 1. 双击安装&#xff0c;点击下一步 2. 勾选接受许可&#xff0c;点击下一步 3. 选择安装位置&#xff0c;点击下一步 4. 用户体验设置&#xff08;可选&#…

2024年PMP考试新考纲-PMBOK第七版-项目管理原则真题解析(续3)

马上就要进入2024年了&#xff0c;要参加2024年PMP一季度考试的小伙伴可以准备起来了。2024年的PMP考试将继续采用新考试大纲&#xff0c;考试内容包括PMBOK第六版、PMBOK第七版和敏捷实践指南&#xff0c;而且敏捷&#xff08;或者叫混合&#xff09;的项目环境将占比超过50%&…

Python的基本数据类型和数据类型的转换

TOC 数据类型 类型查看 type 可以使用type内置函数查看变量所指的对象类型 a1 b1.0 c"1" d1, e[1] f{1:1} g{1}print(type(a)) print(type(b)) print(type(c)) print(type(d)) print(type(e)) print(type(f)) print(type(g))isinstance **如字面意思,isinstance()…