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 <= 12s由小写英文字母、大写英文字母和数字组成
解法
题目解析
- 题目的意思非常简单,给定一个字符串
s - 通过将字符串
s中的每个字母转变大小写,我们可以获得一个新的字符串。 - 返回 所有可能得到的字符串集合 ,以 任意顺序 返回输出。
示例 1:
输入:s = "a1b2" 输出:["a1b2", "a1B2", "A1b2", "A1B2"]
算法原理思路讲解
- 不进⾏处理;
- 若当前字⺟是英⽂字⺟并且是⼤写,将其修改为⼩写;
- 若当前字⺟是英⽂字⺟并且是⼩写,将其修改为⼤写。
一、画出决策树

决策树就是我们后面设计函数的思路
二、设计代码
(1)全局变量
string path;vector<string> ret;
- ret(存储转变大小写,获得一个个新的字符串)
- path(组合的路径记录)
(2)设计递归函数
void dfs(string s, int pos); // 表示现在要处理的元素的下标
- 参数:s(字符串),pos(当前要处理的元素下标);
- 返回值:无;
- 函数作用:查找所有可能的字符串集合,并将其记录在答案列表。;
- 递归结束条件:当前需要处理的元素下标越界,表⽰处理完毕,记录当前状态并返回;
- 判断当前元素是否为数字,若是,对当前元素不进⾏任何处理,直接递归下⼀位元素;
- 判断当前元素是否为⼩写字⺟,若是,将其修改为⼤写字⺟并递归下⼀个元素,递归结束时撤销修改操作;
- 判断当前元素是否为⼤写字⺟,若是,将其修改为⼩写字⺟并递归下⼀个元素,递归结束时撤销修改操作;
以上思路讲解完毕,大家可以自己做一下了
代码实现
- 时间复杂度:O(n×
),其中 n 表示字符串的长度。递归深度最多为 n,所有可能的递归子状态最多为
个,每次个子状态的搜索时间为 O(n),因此时间复杂度为 O(n×
)。
- 空间复杂度:O(n×
)。递归深度最多为 n,。队列中的元素数目最多为
个,每次个子状态的搜索时间为 O(n),因此空间复杂度为 O(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;}
};

相关文章:
LeetCode刷题--- 字母大小写全排列
个人主页:元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.csdnimg.cn/hKh2l 前言:这个专栏主要讲述递归递归、搜索与回…...
165. 小猫爬山(DFS之剪枝与优化)
165. 小猫爬山 - AcWing题库 翰翰和达达饲养了 N 只小猫,这天,小猫们要去爬山。 经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。 翰翰和达达只好花钱让它们…...
【Linux系统基础】(6)在Linux上大数据NoSQL数据库HBase集群部署、分布式内存计算Spark环境及Flink环境部署详细教程
大数据NoSQL数据库HBase集群部署 简介 HBase 是一种分布式、可扩展、支持海量数据存储的 NoSQL 数据库。 和Redis一样,HBase是一款KeyValue型存储的数据库。 不过和Redis设计方向不同 Redis设计为少量数据,超快检索HBase设计为海量数据,…...
多维时序 | MATLAB实CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测
多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测 目录 多维时序 | MATLAB实现CNN-BiGRU-Mutilhead-Attention卷积网络结合双向门控循环单元网络融合多头注意力机制多变量时间序列预测预测效果基本介…...
vs快捷键
ctrlMo 折叠代码块 ctrlML 打开代码块...
linux 内核时间计量方法
定时器中断由系统定时硬件以规律地间隔产生; 这个间隔在启动时由内核根据 HZ 值来编 程, HZ 是一个体系依赖的值, 在 <linux/param.h>中定义或者它所包含的一个子平台文 件中. 在发布的内核源码中的缺省值在真实硬件上从 50 到 1200 嘀哒每秒, 在软件模拟 器中往下到 24.…...
循环神经网络中的梯度消失或梯度爆炸问题产生原因分析(二)
上一篇中讨论了一般性的原则,这里我们具体讨论通过时间反向传播(backpropagation through time,BPTT)的细节。我们将展示目标函数对于所有模型参数的梯度计算方法。 出于简单的目的,我们以一个没有偏置参数的循环神经…...
JWT signature does not match locally computed signature
1. 问题背景 最近在协助团队小盆友调试一个验签问题,结果还“节外生枝”了,原来不是签名过程的问题,是token的问题。 当你看到“JWT signature does not match locally computed signature. JWT validity cannot be asserted and should not…...
vitepress项目使用github的action自动部署到github-pages中,理论上可以通用所有
使用github的action自动部署到github-pages中 创建部署的deploy.yml文件,在项目的根目录下面 .github\workflows\deploy.yml 完整的代码:使用的是pnpm进行依赖安装。 name: 部署VitePresson:push:branches:- docs # 这段是在推送到 docs 分支时触发该…...
Python爬虫---解析---JSONPath
Xpath可以解析本地文件和服务器响应的文件,JSONPath只能解析本地文件 1. 安装jsonpath:pip install jsonpath 注意:需要安装在python解释器相同的位置,例如:D:\Program Files\Python3.11.4\Scripts 2. 使用步骤 2.1 导入&…...
路由器介绍和命令操作
先来回顾一下上次的内容: ip地址就是由32位二进制数组 二进位数就是只有数字0和1组成 网络位:类似于区号,表示区域作用 主机位:类似于号码,表示区域中编号 网络名称:网络位不变,主机位全为0 …...
Hadoop——分布式计算
一、分布式计算概述 1. 什么是计算、分布式计算? 计算:对数据进行处理,使用统计分析等手段得到需要的结果分布式计算:多台服务器协同工作,共同完成一个计算任务2. 分布式计算常见的2种工作模式分散->汇总 (MapReduce就是这种模式)将数据分片,多台服务器各自负责一…...
LaTeX引用参考文献 | Texstudio引用参考文献
图片版教程: 文字版教程: ref.bib里面写参考的文献,ref.bib和document.tex要挨着放,同一个目录里面. 解析一下bib文件格式:aboyeji2023effect是引用文献的关键字,需要在正文document.tex里面使用\cite指令…...
如何在Go中使用模板
引言 您是否需要以格式良好的输出、文本报告或HTML页面呈现一些数据?你可以使用Go模板来做到这一点。任何Go程序都可以使用text/template或html/template包(两者都包含在Go标准库中)来整齐地显示数据。 这两个包都允许你编写文本模板并将数据传递给它们,以按你喜欢的格式呈…...
云原生之深入解析基于FunctionGraph在Serverless领域的FinOps的探索和实践
一、背景 Serverless 精确到毫秒级的按用付费模式使得用户不再需要为资源的空闲时间付费。然而,对于给定的某个应用函数,由于影响其计费成本的因素并不唯一,使得用户对函数运行期间的总计费进行精确的事先估计变成了一项困难的工作。以传统云…...
电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述
电子电器架构(E/E)演化 —— 主流主机厂域集中架构概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。…...
Python常用的几个函数
print()函数:用于打印输出信息到控制台。 input()函数:用于从控制台获取用户输入。 len()函数:用于获取字符串、列表、元组、字典等对象的长度。 range()函数:用于生成一个整数序列,常用于循环中。 type()函数&…...
【Linux系统基础】(2)在Linux上部署MySQL、RabbitMQ、ElasticSearch等各类软件
实战章节:在Linux上部署各类软件 前言 为什么学习各类软件在Linux上的部署 在前面,我们学习了许多的Linux命令和高级技巧,这些知识点比较零散,同学们跟随着课程的内容进行练习虽然可以基础掌握这些命令和技巧的使用,…...
HarmonyOS4.0系统性深入开发01应用模型的构成要素
应用模型的构成要素 应用模型是HarmonyOS为开发者提供的应用程序所需能力的抽象提炼,它提供了应用程序必备的组件和运行机制。有了应用模型,开发者可以基于一套统一的模型进行应用开发,使应用开发更简单、高效。 HarmonyOS应用模型的构成要…...
线下终端门店调研包含哪些内容
品牌渠道一般分为线上和线下,线上的价格、促销信息、店铺优惠机制等都可以通过登录查看,但是线下门店的数据则需要进店巡查,否则无法得到真实的店铺销售数据,当然也有品牌是靠线下的业务团队报备机制获得这些信息,但是…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
