回溯 字母大小寫全排列

題目

給定一個字符串S，通過將字符串S中的每個字母轉(zhuǎn)變大小寫，我們可以獲得一個新的字符串。返回所有可能得到的字符串集合。

示例:

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


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


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

注意：

S 的長度不超過12。 S 僅由數(shù)字和字母組成。

解法一

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 {
    public List<String> letterCasePermutation(String S) {
        char[] sArr = S.toCharArray();
        List<String> result = new LinkedList<>();
        backtrack(0, sArr, result);
        return result;
    }


    public void backtrack(int current, char[] sArr, List<String> result) {
        //如果已經(jīng)處理了最后一個字符，將字符串加到結(jié)果集，返回
        if (current == sArr.length) {
            result.add(new String(sArr));
            return;
        }


        if (sArr[current] >= '0' && sArr[current] <= '9') {//如果為數(shù)字，直接跳過，處理下一個字符
            backtrack(current + 1, sArr, result);
        } else {//如果為字母，則有兩種情況：1.不處理當前字母 2.將當前字母切換大小寫
            //不處理當前字母
            backtrack(current + 1, sArr, result);
            //將當前字母切換大小寫
            sArr[current] = (char)(sArr[current] ^ 32);
            backtrack(current + 1, sArr, result);
        }
    }
}