【LeetCode】字母大小写全排列 Java 题解
题目描述
给定一个字符串 s ,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。
返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
复制代码
思路分析
今天的算法题目字符串类型题目。题目比较清晰,我们可以拆分成两个子问题。一是全排列的问题。二是大小写字母转化的问题。具体到这个问题,频繁修改字符串,我们使用 StringBuilder 类减少无用对象的创建和使用,提升效率。初始化 StringBuilder,然后逐个遍历 s 的字符,判断是否是字母。如果是大写就转换成小写,然后是小写就转换成大写。当 StringBuilder 长度与 s 长度相等时,就是其中一个答案。
对于大小写字母转化的问题,这里主要是使用 ASCII 码的知识,其中 'A' 的 ASCII 的十进制是 97,'a' 的 ASCII 的十进制是 65,中间差值是 32。利用这一性质,我们就可以实现字符的大小写转化,但是写的稍微有一点冗余。我学习官方题解,可以(char) (s.charAt(pos) ^ 32)这个这样完成大小写转化。为什么呢?比如 A 的 ASCII 二进制为 01000010,32 的二进制值为 00100000,异或之后,就可以完成转换。
具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(2 的 n 次方),空间复杂度是 O(n × 2 的 n 次方 )
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/33efe21762a9d46e79d8f4896】。文章转载请联系作者。
评论