784. Letter Case Permutation

Задача

Дана строка s. Меняя регистр каждой буквы, верните все возможные строки.

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

/**
 * Time: O(n * 2^k), где n = длина строки, k = количество букв в строке.
 * Пояснение: для каждой буквы есть 2 выбора (lower/upper) ⇒ всего 2^k комбинаций; чтобы сформировать очередную строку длины n,
 * мы последовательно дописываем символы (в JS это обычно приводит к суммарной работе порядка n на каждую комбинацию).
 *
 * Space: O(n) дополнительной памяти на стек рекурсии + O(n * 2^k) на хранение результата.
 * Пояснение: глубина рекурсии максимум n; в результирующем массиве хранится 2^k строк, каждая длины n.
 */
var letterCasePermutation = function(s) {
    const result = [];
 
    function backtrack(index, current) {
        if (index === s.length) {
            result.push(current);
            return;
        }
 
        const ch = s[index];
 
        if (ch >= '0' && ch <= '9') {
            backtrack(index + 1, current + ch);
        } else {
            backtrack(index + 1, current + ch.toLowerCase());
            backtrack(index + 1, current + ch.toUpperCase());
        }
    }
 
    backtrack(0, '');
    return result;
};