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