784. Letter Case Permutation

题目描述和难度

  • 题目描述：

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

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

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

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

注意：

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

思路分析

求解关键：这道题使用简单的递归回溯就可以求解了。

参考解答

参考解答1

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private void helper(char[] chars, int len, int begin, List<String> res) {
        if (begin == len) {
            res.add(new String(chars));
            return;
        }
        // 不变化的时候递归搜索一次
        helper(chars, len, begin + 1, res);
        if ((chars[begin] + "").matches("[a-zA-Z]")) {
            change(chars, begin);
            // 变化了以后递归搜索一次
            helper(chars, len, begin + 1, res);
        }
    }

    /**
     * 将 chars 数组中 index 数位上的字符改变大小写
     *
     * @param chars
     * @param index
     */
    private void change(char[] chars, int index) {
        if (chars[index] >= 97) {
            chars[index] -= 32;
            return;
        }
        if (chars[index] >= 65) {
            chars[index] += 32;
        }
    }

    public List<String> letterCasePermutation(String S) {
        List<String> res = new ArrayList<>();
        int len = S.length();
        if (len == 0) {
            res.add(S);
            return res;
        }
        char[] chars = S.toCharArray();
        helper(chars, len, 0, res);
        return res;
    }

    public static void main(String[] args) {
        // 97
        System.out.println((int) 'a');
        // 65
        System.out.println((int) 'A');

        Solution solution = new Solution();
        String S = "";
        List<String> letterCasePermutation = solution.letterCasePermutation(S);
        System.out.println(letterCasePermutation);
    }
}

参考解答2：

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    private static final int MASK = 1 << 5;

    private void helper(char[] chars, int len, int begin, List<String> res) {
        if (begin == len) {
            res.add(new String(chars));
            return;
        }
        helper(chars, len, begin + 1, res);
        if (Character.isLetter(chars[begin])) {
            chars[begin] ^= MASK;
            helper(chars, len, begin + 1, res);
        }
    }

    public List<String> letterCasePermutation(String S) {
        List<String> res = new ArrayList<>();
        int len = S.length();
        if (len == 0) {
            res.add(S);
            return res;
        }
        char[] chars = S.toCharArray();
        helper(chars, len, 0, res);
        return res;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0784-letter-case-permutation ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。