Answer

Ответ:

const getPasswordCombination = (input) => {
  const result = [];

  if (!input) {
    return result;
  }

  const phoneDict = new Map([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz'],
  ]);

  const backtrack = (combination, digits) => {
    if (!digits) {
      result.push(combination);
      return;
    }

    // берем буквы по 1й цифре числа
    const digit = digits.substring(0, 1);
    const letters = phoneDict.get(digit);

    // проходим по всем буквам соот-е текущей цифре
    for (let i = 0; i < letters.length; i++) {
      var letter = letters[i];

      // запускаем функцию Backtrack с нашим предположением и след.цифрой
      backtrack(combination + letter, digits.substring(1));
    }
  };

  backtrack('', input);

  return result;
};

Обьяснение:

Самый подходящий алгоритм для этой задачи — это метод поиска с возвратом или Backtracking.

Суть довольна простая: на каждом шаге мы фиксируем текущую букву и запускаем перебор для букв след.цифры. А все полученные результаты мы сохраняем в глобальном результирующем списке. Для удобства фиксации текущей буквы мы просто запускаем рекурсивную функцию.

Итак, алгоритм будет следующим:

1. Создадим таблицу ключ-значение — <цифра, строка с буквами>. Словарь будет содержать пары с ключами от 2 до 9.
2. Функция backtrack(combination, digits) принимаем 2 параметра: набор букв, а также набор текущих цифр, ктр осталось проверить.
3. — Если набор текущих цифр пустой, значит у нас уже есть 1 комбинация букв, ктр мы можем поместить в результирующий список.
4. — Иначе, из таблицы мы получаем набор букв для текущей цифры. Проходим по этому набору и добавляем букву к текущей комбинации и запускаем рекурсивную фукнцию, не забывая убрать текущую цифру из digits.

Таким образом, рекурсивно мы соберем всевозможные буквенные комбинации, ктр могут быть получены по заданному набору цифр.

Код для проверки:

const getPasswordCombination = (input) => {
  const result = [];

  if (!input) {
    return result;
  }

  const phoneDict = new Map([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz'],
  ]);

  const backtrack = (combination, digits) => {
    if (!digits) {
      result.push(combination);
      return;
    }

    // берем буквы по 1й цифре числа
    const digit = digits.substring(0, 1);
    const letters = phoneDict.get(digit);

    // проходим по всем буквам соот-е текущей цифре
    for (let i = 0; i < letters.length; i++) {
      var letter = letters[i];

      // запускаем функцию Backtrack с нашим предположением и след.цифрой
      backtrack(combination + letter, digits.substring(1));
    }
  };

  backtrack('', input);

  return result;
};

console.log(getPasswordCombination('2')); // [ 'a', 'b', 'c' ]

console.log(getPasswordCombination('23')); // ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf'];