Два года назад во время собеседования по кодированию в FAANG меня попросили напечатать все возможные буквенные комбинации телефонного номера. Я был шокирован и очень старался во время интервью, но в конце концов сдался. Сегодня я снова возвращаюсь к этому вопросу и, наконец, знаю, как это сделать.

Давайте посмотрим на вопрос,

Прежде чем приступить к работе, нам нужно знать несколько вещей.

  1. Будет ли серия одинаковых чисел, в которой длина больше 4?
    да, поэтому для 22222 результат будет
    2 2 2 2 2- ›AAAAA
    22 2 2 2- ›BAAA
    2 22 2 2-› ABAA
    222 2 2- ›CAA
    …… (и т. Д.)
  2. Вход содержит только числа?
    да, только 0–9
  3. Если я получу 111111, результатом будет пустой массив?
    нет, 1 означает пробел, если вы дадите мне 111111, функция должна вернуть 6 пробелов.

Как это сделать?

Первое, что приходит мне в голову, это

  1. разделите ввод на группу одинаковых чисел, так что для ввода «222233442» у нас будет [«22222», «33», «44», «2»]
  2. а затем мы используем рекурсию, чтобы получить все возможности объединения 2, 22 и 222 в 22222. Это похоже на задачу Обмен монет, нахождение всех комбинаций монет, которые могут дать определенную сумму.

3. наконец, мы можем объединить комбинации из 2) в наш результат

compute
[
  [AAA, BA, AB, C], <- 222
  [D],              <- 3
]
into
[AAAD, BAD, ABD, CD]

Вот полный фрагмент моего подхода:

Предыдущий:

Общий подход к подмножествам, комбинациям и перестановкам

Я надеюсь, что это помогает

Кстати, если вас интересуют алгоритмы, то вот мое путешествие по ежедневному челленджу AlGoDaily. Я также включил приведенный выше фрагмент в репо, пожалуйста, не стесняйтесь создавать для него новую проблему / пул-реквест. Спасибо.