Longest Palindromic Substring

Средняя№5из центра наружу

Дана строка. Нужно найти в ней самый длинный кусок из идущих подряд символов, который читается одинаково слева направо и справа налево. Наш пример: «xabbay» — ответ «abba».

5 Longest Palindromic SubstringРазбор · 1×

Пример: «xabbay». Из каждого из 11 центров — 6 букв и 5 промежутков между ними — указатели расходятся наружу, пока буквы совпадают.

0x1a2b3b4a5yлучшийs[0 .. 0]x
под указателемпалиндром вокруг центрасамый длинный пока

Любая одна буква — палиндром: пока лучший кусок s[0 .. 0] = «x»

01/91
сначала · назад · пуск · шаг
Скорость
1function longestPalindrome(s):
2 start = 0; end = 0 // best: s[start .. end]
3 for center from 0 to 2 * len(s) - 2:
4 left = floor(center / 2)
5 right = left + center mod 2 // odd: a gap
6 while left >= 0 and right < len(s):
7 if s[left] != s[right]: break
8 left = left - 1; right = right + 1
9 if right - left - 1 > end - start + 1:
10 start = left + 1; end = right - 1
11 return s[start .. end]
состояние
center
–
left
–
right
–
start
0
end
0
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Палиндром зеркален относительно своей середины. Значит, начинаем с середины и шагаем наружу, пока две буквы по краям совпадают.
  2. Середина — это буква, когда длина нечётная («aba»), и промежуток между двумя буквами, когда чётная («abba»). В строке из n букв n букв и n − 1 промежутков: 2n − 1 центров. Перебрав их все, не пропустим ни одного палиндрома.
  3. Рост останавливается на первой несовпавшей паре: любой кусок длиннее вокруг этого центра тоже содержит эту пару, значит, и он не палиндром.

Сложность

Время O(n²): 2n − 1 центров, и из каждого указатели делают не больше n / 2 шагов. Память O(1), не считая самого ответа: храним только start и end, а кусок вырезаем один раз в конце. Алгоритм Манакера находит ответ за O(n), но на собеседовании его ждут редко.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.