784. Letter Case Permutation

Problem

Tags: String, Backtracking, Bit Manipulation

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.

Code

JS

// 784. Letter Case Permutation (5/13/53742)
// Runtime: 92 ms (62.83%) Memory: 42.54 MB (94.56%) 

/**
 * @param {string} s
 * @return {string[]}
 */
function letterCasePermutation(s) {
    const idxs = [...s].map((char, idx) => (char.match(/[a-z]/i) ? idx : null)).filter((idx) => idx !== null);
    const result = [];
    backtrack(0, s.toLowerCase());
    return result;

    function backtrack(idx, current) {
        if (idx === idxs.length) return result.push(current);
        backtrack(idx + 1, current);
        backtrack(idx + 1, current.slice(0, idxs[idx]) + current[idxs[idx]].toUpperCase() + current.slice(idxs[idx] + 1));
    }
}