784. Letter Case Permutation.md

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

C++ version

• Method 1:

   class Solution {
   	vector<string> res_;
   	void dfs(string s, int index, string temp){
   		if(index == s.length()) res_.emplace_back(temp);
   		else{
   			if(!isalpha(s[index])){
   				dfs(s, index + 1, temp + s[index]);
   			}else{
   				dfs(s, index + 1, temp + (char)tolower(s[index]));
   				dfs(s, index + 1, temp + (char)toupper(s[index]));
   			}
   		}
   	}
   public:
   	vector<string> letterCasePermutation(string S) {
   		dfs(S, 0, "");
   		return res_;
   	}
   };