784. Letter Case Permutation

Leetcode Backtracking Bit Manipulation

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:

• $S$ will be a string with length between 1 and 12.
• $S$ will consist only of letters or digits.

分析

使用回溯法:

public List<String> letterCasePermutation(String S) {
    List<String> list = new ArrayList<>();
    if (S == null) return list;
    letterCasePermutation(list, new StringBuilder(), S, 0);
    return list;
}


private void letterCasePermutation(List<String> list, 
            StringBuilder sb, String S, int index){
    // base case
    if (index == S.length()) {list.add(sb.toString()); return;}
    // chosen
    char c = S.charAt(index);
    if (!Character.isLetter(c)) {  // numbers
        sb.append(c);
        letterCasePermutation(list, sb, S, index + 1);      // explore
        sb.deleteCharAt(sb.length() - 1);                   // unchosen
    } else {
        sb.append(Character.toLowerCase(c));
        letterCasePermutation(list, sb, S, index + 1);
        sb.deleteCharAt(sb.length() - 1);

        sb.append(Character.toUpperCase(c));
        letterCasePermutation(list, sb, S, index + 1);
        sb.deleteCharAt(sb.length() - 1);
    }
}