Пример решения задачи #5. Python LeetCode, Longest Palindromic Substring

Вариант решения задачи на языке программирования Python с LeetCode.
Название задачи: Longest Palindromic Substring.
Категория: Алгоритмы.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Задача на алгоритмы. Дана строка s, верните самую длинную палиндромную подстроку в s.

Решение:

Python

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # Если строка пустая или состоит из одного символа, возвращаем её саму
        if len(s) <= 1:
            return s

        # Инициализируем переменные для хранения начала и максимальной длины палиндрома
        start = 0
        max_length = 1

        # Вспомогательная функция для расширения границ палиндрома
        def expand_around_center(left, right):
            # Расширяем границы, пока символы слева и справа равны
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # Возвращаем начало и длину найденного палиндрома
            return left + 1, right - left - 1

        # Проходим по каждому символу строки
        for i in range(len(s)):
            # Проверяем палиндром нечётной длины (центр в одном символе)
            left, length = expand_around_center(i, i)
            if length > max_length:
                start = left
                max_length = length

            # Проверяем палиндром чётной длины (центр между двумя символами)
            if i + 1 < len(s) and s[i] == s[i + 1]:
                left, length = expand_around_center(i, i + 1)
                if length > max_length:
                    start = left
                    max_length = length

        # Возвращаем найденный палиндром
        return s[start:start + max_length]

# Пример использования
solution = Solution()
print(solution.longestPalindrome("babad"))  # Вывод: "bab" или "aba"
print(solution.longestPalindrome("cbbd"))   # Вывод: "bb"

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

Базовый случай:
Если строка пустая или состоит из одного символа, сразу возвращаем её.

Инициализация:
Задаем начальные значения для начала (start) и максимальной длины (max_length) палиндрома.

Функция расширения:
expand_around_center находит самый длинный палиндром, начиная с заданного центра (индексы left и right).

Цикл по символам:
Для каждого символа проверяем два случая:
Палиндром нечётной длины (центр в одном символе).
Палиндром чётной длины (центр между двумя символами).

Обновление результата:
Если найденный палиндром длиннее текущего, обновляем start и max_length.

Возврат результата:
После завершения цикла возвращаем подстроку с использованием start и max_length.

Этот подход эффективно находит самый длинный палиндром за время O(n²) , где n — длина строки.

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