图解LeetCode——784. 字母大小写全排列（难度：中等）

一、题目

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

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

二、示例

2.1> 示例 1：

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

2.2> 示例 2:

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

提示:

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

三、解题思路

3.1> 回溯

首先，根据题目描述，我们要将遇到的所有“英文字母”执行大小写转换，并将每一个变换后的字符串保存下来，作为最终结果输出。那么，我们可以采用回溯的方式对这道题进行处理。针对于回溯的实现，其实是有固定的模板的，我们以下图中的字符串为例：

循环遍历整个字符串s的每个字符
步骤1：发现下标为i处是英文字母时，我们以第0处是a为例，则将a变为A。
步骤2：执行递归操作，处理下一个英文字母，即：第1层以A为基础，去处理下一个英文字母b。
步骤3：执行回溯操作，将下标为0的英文字母a进行还原操作，即：从A还原为a。

详细的操作，请见下图所示：

3.2> 利用List进行模拟

除了回溯方法之外，我们也可以先将s=“a1b2c”字符串放入到List中，然后遍历整个字符串s，当发现下标i处是英文字母后，执行如下操作：

步骤1：将当前List中所有的字符串都复制出来一份。
步骤2：将下标为i处的字符执行大小写转换。即：如果是大写则变为小写，如果是小写则变为大写。
步骤3：然后再将转换后的字符串添加到List中。

具体操作如下图所示：

四、代码实现

4.1> 利用回溯

class Solution {
    public List<String> letterCasePermutation(String s) {
        return buildStr(0, new ArrayList(), s.toCharArray());
    }
    private List<String> buildStr(int start, List<String> result, char[] sc) {
        result.add(new String(sc));
        for (int i = start; i < sc.length; i++) {
            if (sc[i] < 'A') continue; // sc[i]是数字，则不需要变化
            if (sc[i] >= 'a') {
                sc[i] = (char) (sc[i] - 32); // 小写转大写
                buildStr(i + 1, result, sc);
                sc[i] = (char) (sc[i] + 32); // 回溯
            } else {
                sc[i] = (char) (sc[i] + 32); // 大写转小写
                buildStr(i + 1, result, sc);
                sc[i] = (char) (sc[i] - 32); // 回溯
            }
        }
        return result;   
    }   
}

4.2> 利用List进行模拟

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> result = new ArrayList();
        result.add(s);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < 'A') continue;
            int size = result.size();
            for (int j = 0; j < size; j++) {
                char[] ic = result.get(j).toCharArray();
                if (ic[i] >= 'a') ic[i] = (char) (ic[i] - 32); // 小写转大写
                else ic[i] = (char) (ic[i] + 32); // 大写转小写
                result.add(new String(ic));
            }
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」