Letter Case Permutation

Problem

Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.

Example 1:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

Example 2:

Input: s = "3z4"
Output: ["3z4","3Z4"]

Constraints:

1 <= s.length <= 12
s consists of lowercase English letters, uppercase English letters, and digits.

Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var letterCasePermutation = function(s) {
    const res = [];
    backtrack(s, res, "", 0);
    return res;
};

var backtrack = function(s, res, path, index) {
    if (index === s.length) {
        res.push(path);
        return;
    }
    const c = s[index];
    if (isDigit(c)) {
        backtrack(s, res, path + c, index + 1);
    } else {
        backtrack(s, res, path + c.toUpperCase(), index + 1);
        backtrack(s, res, path + c.toLowerCase(), index + 1);
    }
};

var isDigit = function(c) {
    return "0" <= c && c <= "9";
};

We will implement a backtracking (DFS) solution. We recursively build up all possible transformations of s one character at a time (stored as path at each step). If the current character is a digit, no change is required; otherwise, it must be a letter, and so we make two recursive calls, one for uppercase and one for lowercase.

Problem​

Solution​

Problem

Solution