LeetCode 784. 字母大小写全排列

784. 字母大小写全排列

题目

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

示例:

输入: S = "a1b2"
输出: ["a1b2", "a1B2", "A1b2", "A1B2"]

输入: S = "3z4"
输出: ["3z4", "3Z4"]

输入: S = "12345"
输出: ["12345"]

注意：

• S 的长度不超过12。
• S 仅由数字和字母组成。

题解：

一、 利用循环来做，对原字符串进行循环遍历。如果遇到数字就直接加，遇到的是字母就复制一组数组，分别以大写和小写拼接到数组末尾。

class Solution {
    public List<String> letterCasePermutation(String S) {
        List<StringBuilder> ans = new ArrayList();
        ans.add(new StringBuilder());

        for (char c: S.toCharArray()) {
            int n = ans.size();
            if (Character.isLetter(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.add(new StringBuilder(ans.get(i)));
                    ans.get(i).append(Character.toLowerCase(c));
                    ans.get(n+i).append(Character.toUpperCase(c));
                }
            } else {
                for (int i = 0; i < n; ++i)
                    ans.get(i).append(c);
            }
        }

        List<String> finalans = new ArrayList();
        for (StringBuilder sb: ans)
            finalans.add(sb.toString());
        return finalans;
    }
}

二、利用递归来做，有人说上面的循环就是递归的形式。

class Solution {
    List<String> list;
    public List<String> letterCasePermutation(String S) {
        list = new ArrayList<>();
        recurse(S.toCharArray(), 0);
        return list;
    }
    public void recurse(char[] chars, int idx){
        if(idx == chars.length){
            list.add(new String(chars));
            return;
        }
        recurse(chars, idx + 1);
        if(chars[idx] >= 'A'){
            chars[idx] = chars[idx] < 'a'? (char)(chars[idx] + 32): (char)(chars[idx] - 32);
            recurse(chars, idx + 1);
        }
    }
}

三、利用回溯来做