Letter Case Permutation

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 at most 12. S will consist only of letters or digits.

Solution : Backtracking

To find all permutations we need to consider two cases for each chracter in string. We can use an integer to mark the current position, if the position is equal to the size of the string, then we find a solution.

For each position, we first directly move forward one posiiton without any changes to the character.

If the character is a alphabet, then we modify the character to its opposite case.

void backtrack(int i, string &S, vector<string> &ans) {
    if (i == S.size()) {
        ans.push_back(S);
        return;
    }

    backtrack(i+1, S, ans);

    if (isalpha(S[i])) {
        S[i] = islower(S[i]) ? toupper(S[i]) : tolower(S[start]);
        backtrack(i+1, S, ans);            
    }
}

vector<string> letterCasePermutation(string S) {
    vector<string> ans;
    backtrack(0, S, ans);
    return ans;
}