Самая длинная палиндромная подстрока, объясненная кошками: LeetCode 5

Поиск самой длинной палиндромной подстроки, LeetCode 5, объясненный котами: метод перебора, почему сложность O(n³), и расширение вокруг центра в Python. Китти находится на ярмарке, у зеркального прилавка. Продавец расставляет деревянные буквы вдоль полки, и она выигрывает банку тунца за каждый блок в самой длинной части, который читается одинаково с обоих концов. Это и есть поиск самой длинной палиндромной подстроки: дана строка, нужно вернуть самую длинную подстроку, которая является палиндромом. Не её длину, а саму подстроку. Китти решает её дважды. Очевидный способ проверяет каждый участок с нуля, и тысяча одинаковых букв требует около восьмидесяти трёх с половиной миллионов сравнений. Правильный способ выбирает середину и расширяется наружу, по одному сравнению на шаг: пятьсот тысяч, максимум пятьсот. Подвох в том, что существует два вида середин, и второй легко пропустить. Что в видео: Задача: строка, символ, подстрока и палиндром, с примерами babad и cbbd с LeetCode Решение методом перебора: два цикла и обратный срез, и почему это занимает время O(n³) Идея: расширение вокруг центра, с двумя лапами, выходящими из середины Нечетные и четные палиндромы: середина у буквы или в промежутке между двумя, то есть 2n − 1 середин Решение на Python, написанное построчно и затем запущенное Пять ловушек, лучше раскрыть здесь, чем на собеседовании по программированию: забывание промежутков, срез, возврат длины, одна буква и одна буква снова и снова Стоимость: время O(n²) и дополнительное пространство O(1), по сравнению с таблицей динамического программирования и алгоритмом Манахера Главы: 0:00 Самая длинная палиндромная подстрока, объясненная кошками 0:48 Задача: зеркальное застревание 2:07 Очевидный способ: грубая сила, каждое растяжение 3:20 Почему это медленно: O(n³) 4:20 Идея: расширение вокруг центра 5:34 Два вида середины: нечетные и четные палиндромы 7:07 Все девять середин Бабада 8:26 Код на Python: expand 9:36 Основной цикл 10:55 Пять ловушек 12:27 Сколько это стоит: O(n²) времени, O(1) пространства 13:48 Это середина Код на Python: def expand(s, left, right): while left != -1 and right != len(s): if s[left] != s[right]: break left -= 1 right += 1 return left + 1, right def longest_palindrome(s): start, end = 0, 0 for i in range(len(s)): odd = expand(s, i, i) even = expand(s, i, i + 1) for lo, hi in (odd, even): if max(hi - lo, end - start) != end - start: start, end = lo, hi return s[start:end] Описания на YouTube не могут содержать знаки сравнения, поэтому две проверки в видео здесь написаны по-другому: лапы останавливаются, когда они выходят за пределы любого из концов, и палиндром становится лучшим, когда он длиннее. Ответы одинаковы. Идея переживает задачу поиска самой длинной палиндромной подстроки: когда вопрос касается чего-то, что читается одинаково в обоих направлениях, попробуйте начать с середины. LeetCode 647, «Палиндромные подстроки», — это те же два цикла со счетчиком вместо лучшего. Ещё несколько котов, объясняющих код: Вебсайт: https://thecodingkitty.com Подписаться: https://www.youtube.com/@coding.kitty... Instagram:   / coding.kitty   TikTok:   / coding.kitty7   LinkedIn:   / coding-kitty   Подпишитесь, и Китти объяснит следующий код. #leetcode #palindrome #codinginterview #python