Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:
Input: S = "a1b2"
Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"
Output: ["3z4", "3Z4"]

Input: S = "12345"
Output: ["12345"]

Note:

• Swill be a string with length between1and12.
• Swill consist only of letters or digits.

没啥多说的，backtracking

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

        char[] cs = S.toCharArray();

        helper(res, 0, cs);

        return res;
    }

    public void helper(List<String> res, int start, char[] cs) {
        if(start == cs.length)
            return;

        int i = start;
        while(i < cs.length && (cs[i] >= '0' && cs[i] <= '9'))
            i++;

        if(i == cs.length)
            return;

        if(cs[i] >= 'a' && cs[i] <= 'z') {
            cs[i] = (char) (cs[i] - 'a' + 'A');
            res.add(String.valueOf(cs));
            helper(res, i + 1, cs);
            cs[i] = (char) (cs[i] - 'A' + 'a');
            helper(res, i + 1, cs);
        }
        if(cs[i] >= 'A' && cs[i] <= 'Z') {
            cs[i] = (char) (cs[i] - 'A' + 'a');
            res.add(String.valueOf(cs));
            helper(res, i + 1, cs);
            cs[i] = (char) (cs[i] - 'a' + 'A');
            helper(res, i + 1, cs);
        }
    }
}