Решение задачи #17. Python LeetCode, Letter Combinations of a Phone Number

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Python LeetCode, Letter Combinations of a Phone Number.
Сложность: Средняя.
Статус решения: "Решено".

Задача относится к алгоритмическим задачам на комбинаторику и рекурсивный перебор (backtracking).

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

Решение:

Python

class Solution(object):
    def letterCombinations(self, digits):
        """
        Функция возвращает все возможные комбинации букв, соответствующие цифрам на телефонной клавиатуре.
        
        :type digits: str - входная строка с цифрами от 2 до 9
        :rtype: List[str] - список строк с комбинациями букв
        """
        
        # Проверяем пустой ввод
        if not digits:
            return []
        
        # Создаем словарь соответствия цифр буквам
        digit_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        
        # Инициализируем список для хранения результатов
        result = []
        
        # Рекурсивная функция для генерации комбинаций
        def backtrack(index, current_str):
            """
            Вспомогательная функция для рекурсивного перебора комбинаций.
            
            :param index: int - текущий индекс в строке digits
            :param current_str: str - текущая формируемая строка
            """
            # Если достигли конца цифр, добавляем комбинацию в результат
            if index == len(digits):
                result.append(current_str)
                return
            
            # Получаем текущую цифру и соответствующие ей буквы
            current_digit = digits[index]
            letters = digit_map[current_digit]
            
            # Перебираем все буквы и рекурсивно вызываем функцию для следующей цифры
            for letter in letters:
                backtrack(index + 1, current_str + letter)
        
        # Запускаем рекурсию с начальными параметрами
        backtrack(0, "")
        
        return result

Объяснение кода

Проверка ввода:
Сначала проверяем, не пустая ли строка digits. Если пустая - сразу возвращаем пустой список.

Словарь соответствий:
Создаем словарь digit_map, где каждой цифре от 2 до 9 соответствуют буквы, как на телефонной клавиатуре:

2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

Рекурсивная функция backtrack:

Базовый случай:
Когда индекс достигает длины строки digits, текущая комбинация добавляется в результат.

Рекурсивный случай:
Для текущей цифры берем все соответствующие буквы и для каждой буквы рекурсивно вызываем функцию для следующей цифры, добавляя текущую букву к строке.

Запуск рекурсии:
Начинаем процесс с индекса 0 и пустой строки.

Возврат результата:
После завершения всех рекурсивных вызовов возвращаем накопленный результат.

Пример использования:

Python

sol = Solution()
print(sol.letterCombinations("23")) 
# Вывод: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

Особенности решения

Используется метод backtracking (возврат с проверкой)

Временная сложность:
O(3^N × 4^M), где N - количество цифр с 3 буквами, M - с 4 буквами

Пространственная сложность:
O(N) для хранения рекурсивного стека вызовов

Решение соответствует стилю задач LeetCode с использованием класса Solution и эффективно перебирает все возможные комбинации, используя рекурсию, является классическим подходом к подобным задачам на комбинаторику.

Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.

Источник решения: hdhai.com