Условие

Дана строка, содержащая цифры от 2 до 9 включительно. Необходимо вернуть все возможные комбинации букв, которые могут соответствовать этим цифрам. Ответ может быть представлен в любом порядке.

Ниже приведено соответствие цифр и букв на телефоне. Обратите внимание, что цифра 1 не соответствует никаким буквам.

Примеры

Пример 1:

Вход: "23"
Выход: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Пример 2:

Вход: ""
Выход: []

Пример 3:

Вход: "2"
Выход: ["a", "b", "c"]

Решение

Для решения задачи мы можем использовать рекурсивный подход. Мы можем перебирать все буквы, соответствующие первой цифре в строке digits и затем рекурсивно вызывать функцию letter_combinations для оставшейся части строки digits. Затем мы объединяем все возможные комбинации букв, полученные из рекурсивных вызовов, с комбинациями букв, полученными из первой цифры, и возвращаем их.

Объяснение

Рассмотрим пример вызова функции letter_combinations("23").

1. Мы начинаем с первой цифры "2". Согласно таблице выше, соответствующие буквы это "abc".
2. Для каждой из букв "a", "b" и "c" мы вызываем рекурсивную функцию letter_combinations("3").
3. При вызове функции letter_combinations("3") мы начинаем с первой цифры "3". Согласно таблице выше, соответствующие буквы это "def".
4. Для каждой из букв "d", "e" и "f" мы вызываем рекурсивную функцию letter_combinations("").
5. При вызове функции letter_combinations("") мы не можем найти никаких дополнительных букв, поэтому мы возвращаем пустой список.