写点什么

【LeetCode】字母大小写全排列 Java 题解

作者:Albert
  • 2022-11-18
    北京
  • 本文字数:980 字

    阅读完需:约 3 分钟

题目描述

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


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


示例 1:
输入:s = "a1b2"输出:["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
输入: s = "3z4"输出: ["3z4","3Z4"]
复制代码

思路分析

  • 今天的算法题目字符串类型题目。题目比较清晰,我们可以拆分成两个子问题。一是全排列的问题。二是大小写字母转化的问题。具体到这个问题,频繁修改字符串,我们使用 StringBuilder 类减少无用对象的创建和使用,提升效率。初始化 StringBuilder,然后逐个遍历 s 的字符,判断是否是字母。如果是大写就转换成小写,然后是小写就转换成大写。当 StringBuilder 长度与 s 长度相等时,就是其中一个答案。

  • 对于大小写字母转化的问题,这里主要是使用 ASCII 码的知识,其中 'A' 的 ASCII 的十进制是 97,'a' 的 ASCII 的十进制是 65,中间差值是 32。利用这一性质,我们就可以实现字符的大小写转化,但是写的稍微有一点冗余。我学习官方题解,可以(char) (s.charAt(pos) ^ 32)这个这样完成大小写转化。为什么呢?比如 A 的 ASCII 二进制为 01000010,32 的二进制值为 00100000,异或之后,就可以完成转换。

  • 具体实现代码如下,供参考。

通过代码

class Solution {    public List<String> letterCasePermutation(String s) {        List<String> ans = new ArrayList<String>();        Queue<StringBuilder> queue = new ArrayDeque<StringBuilder>();        queue.offer(new StringBuilder());        while (!queue.isEmpty()) {            StringBuilder curr = queue.peek();            if (curr.length() == s.length()) {                ans.add(curr.toString());                queue.poll();            } else {                int pos = curr.length();                if (Character.isLetter(s.charAt(pos))) {                    StringBuilder next = new StringBuilder(curr);                    next.append((char) (s.charAt(pos) ^ 32));                    queue.offer(next);                }                curr.append(s.charAt(pos));            }        }        return ans;    }}
复制代码

总结

  • 上述算法的时间复杂度是 O(2 的 n 次方),空间复杂度是 O(n × 2 的 n 次方 )

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 4
用户头像

Albert

关注

数据结构和算法爱好者 2019-09-29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】字母大小写全排列Java题解_算法_Albert_InfoQ写作社区