打基础之LeetCode算法题第57篇:两种方法解字母大小写全排列问题

bigegpt 2024-10-14 08:19 10 浏览

一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧，一开始就弄些重量级的，什么人工智能，机器学习的算法，还要有大量的数学以及优化的知识，小白们估计会很郁闷，当然我也不一定能做出来对吧。我计划每题给出两种语言的解决方案，一种静态语言，一种动态语言。我选择C语言，Python和Java作为实现语言，由于篇幅有限，其他语言的实现有兴趣的朋友请自己尝试。

LeetCode 784. 字母大小写全排列（Surface Area of 3D Shapes）

问题描述：

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：

C语言实现：

解决这个问题的方法有很多，我之前的实现是用BFS（广度优先算法），但是BFS需要构筑一个队列，整个代码下来要八十多行。关于BFS的算法思路是先将原字符串入队列，然后遍历原字符串每个字符，如果遇到字母就开始按顺序弹出队列中的元素，且对于每个元素转换该字符的大小写生成新字符串再入队列。如此一直到遍历完所有的字符。

我们这里给出的代码是另一个解决方法，该方法不是用替换的方法，而是用逐步填充的办法。

详细代码如下：

首先构造一个空字符串填充到res[0]，依然是要遍历原字符串每个字符，如果遇到数字就直接填充到每一个新字符串后面；如果遇到字母就构造一个临时数组，数组元素是该字母的大写和小写。

变量count记录的是新字符串的数量，代码18行的循环就是逐步填充。这里有一个细节，举个例子，假如当前count = 2, res[0] = "b", S[i] = 'c'，lowerAndUpper内容就是['c'，'C']。这个时候除了bc外还会产生的字符串bC，我们的做法是新的字符串bC保存到res[count]的位置。

最后说说效率的问题。我这里给出的两个算法的效率都不好。后面这个算法的最坏时间复杂度是O(n^2)。

暂时还没想到算法复杂度更好的算法，有时间可以思考思考。

也欢迎大家在评论区留言，说出你的思路。

python语言的实现：

python的实现完全参考C语言的第二个实现方法。只是用python实现起来要简单的多。

代码如下：

Java语言的实现：

Java的实现我使用的是BFS算法，因为用java库中的队列接口实现起来比C语言要简单的多。关于具体的实现原理，见C语言实现里的描述。

代码如下：

java大写转小写

打基础之LeetCode算法题第57篇:两种方法解字母大小写全排列问题

问题描述：

示例：

C语言实现：

python语言的实现：

Java语言的实现：

相关推荐

idea本地配置连接远程hadoop集群的一些网络问题解决汇总

无缓存不行?例行升级的入门级阿斯加特AN2 SSD装机点评

Ceph运维手册(基于P版本)

Docker 命令大全（docker命令大全记录表）

替代Docker build的Buildah简单介绍

Docker Desktop安装使用指南:零基础教程

大数据开发前要做什么准备?8台Hadoop服务器进行集群规划前配置

Tensorflow分类loss函数总结 tensorflow绘制loss曲线

R语言学习笔记(七) -离散型数据的模型预测2

iOS Runtime详解