Два года назад во время собеседования по кодированию в FAANG меня попросили напечатать все возможные буквенные комбинации телефонного номера. Я был шокирован и очень старался во время интервью, но в конце концов сдался. Сегодня я снова возвращаюсь к этому вопросу и, наконец, знаю, как это сделать.
Давайте посмотрим на вопрос,
Прежде чем приступить к работе, нам нужно знать несколько вещей.
- Будет ли серия одинаковых чисел, в которой длина больше 4?
да, поэтому для 22222 результат будет
2 2 2 2 2- ›AAAAA
22 2 2 2- ›BAAA
2 22 2 2-› ABAA
222 2 2- ›CAA
…… (и т. Д.) - Вход содержит только числа?
да, только 0–9 - Если я получу 111111, результатом будет пустой массив?
нет, 1 означает пробел, если вы дадите мне 111111, функция должна вернуть 6 пробелов.
Как это сделать?
Первое, что приходит мне в голову, это
- разделите ввод на группу одинаковых чисел, так что для ввода «222233442» у нас будет [«22222», «33», «44», «2»]
- а затем мы используем рекурсию, чтобы получить все возможности объединения 2, 22 и 222 в 22222. Это похоже на задачу Обмен монет, нахождение всех комбинаций монет, которые могут дать определенную сумму.
3. наконец, мы можем объединить комбинации из 2) в наш результат
compute [ [AAA, BA, AB, C], <- 222 [D], <- 3 ] into [AAAD, BAD, ABD, CD]
Вот полный фрагмент моего подхода:
Предыдущий:
Общий подход к подмножествам, комбинациям и перестановкам
Я надеюсь, что это помогает
Кстати, если вас интересуют алгоритмы, то вот мое путешествие по ежедневному челленджу AlGoDaily. Я также включил приведенный выше фрагмент в репо, пожалуйста, не стесняйтесь создавать для него новую проблему / пул-реквест. Спасибо.