784. Letter Case Permutation

784. Letter Case Permutation

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);
              }
          }
      }
      }