Применение рекурсии для решения алгоритмических задач. «Letter Combinations of a Phone Number»

Помните, раньше были кнопочные телефоны, и сообщения нужно было вводить по букве, нажимая на клавиши несколько раз, пока не выберешь нужную. Сегодняшняя задача как раз про это — Альбина в новом эпизоде столкнется с этой задачей.

#LeetCode #python #АлгоритмическаяКачалка #Программирование #Алгоритмы

[garyroach]

Спасибо за полезное видео!
Очень бы хотелось посмотреть видео с разбором насколько Product быстрее)

[constantine]

По времени: количество итоговых комбинации не превосходит 4^n, и каждая из них состоит из n букв. То есть у нас O(n 4ⁿ) операций добавления буквы. Каждая такая операция стоит линейного времени, так что в итоге T = O(n² 4ⁿ)

Можно ли улучшить? Можно, но не принципиально. Всё упирается в объём результата. Если выделить память заранее, можно избавиться от квадрата, но самый страшный множитель -- экспоненциальный -- никуда не денется.

[karakurik]

medium lvl Constraints:

0 <= digits.length <= 4🤣