Question:

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.

Solution:

  • Method 1: backtrace
    • Maintain a temp variable to hold state, can use List or StringBuilder.
    • Add current possible variable to temp.
    • backtrace
    • remove current variable from temp and put next possible variable. 
        class Solution {
  public List<String> letterCasePermutation(String S) {
      List<String> result = new ArrayList<>();
      if(S.length() == 0){
          result.add("");
          return result;   
      }
      dfs(result, S.toCharArray(), 0, new StringBuilder());
      return result;
  }
  private void dfs(List<String> result, char[] arr, int index, StringBuilder sb){
      if(index == arr.length){
          result.add(sb.toString());
      }else if(index < arr.length){
          if(arr[index] >= '0' && arr[index] <= '9'){
              sb.append(arr[index]);
              dfs(result, arr, index + 1, sb);
              sb.deleteCharAt(index);
          }else{
              sb.append(Character.toUpperCase(arr[index]));
              dfs(result, arr, index + 1, sb);
              sb.deleteCharAt(index);
              sb.append(Character.toLowerCase(arr[index]));
              dfs(result, arr, index + 1, sb);
              sb.deleteCharAt(index);
          }
      }
  }
  }