смысл названия
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Link: https://leetcode.com/problems/longest-palindromic-substring/
перевести
Дана строка s, найти в ней самую длинную палиндромную подстроку. Можно предположить, что длина s-строки не превосходит 1000.
Образец
Example 1:
Input: "babad"Output: "bab"Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"Output: "bb"
анализировать
Хотя сложность этого вопроса в LeetCode средняя, на самом деле это непросто, и нам трудно придумать наилучшее решение собственным мышлением.
Давайте пока отложим в сторону различные алгоритмы и начнем с самого простого метода. Самый простой способ — это, конечно, перебор методом грубой силы, но эта проблема отличается от предыдущей проблемы со строками. При насильственном перечислении нам не нужно перечислять все начальные позиции, а затем определять, является ли подстрока палиндромом. На самом деле, мы можем использовать свойство, что обе стороны палиндрома равны, чтобы напрямую перечислить положение центра палиндрома и распространить его на обе стороны, если две стороны равны. Таким образом, нам нужно перечислить не более n центров палиндромов, и каждое перечисление проходит не более n раз. Таким образом, окончательная сложность
.
Опытные студенты могут среагировать на эту сложность, когда увидят ее, что, очевидно, не является оптимальным решением. Но для текущей проблемы, хотя насильственное перечисление не является лучшим решением, на самом деле это хорошее решение. Оно не так плохо, как мы думаем. Если вы не верите, давайте взглянем на другое решение, которое выглядит намного выше. .
Динамическое программирование (DP)
В этом вопросе также есть хитрость, использующая свойства строк-палиндромов: для строки S, если мы перевернем ее, чтобы получить S_, очевидно, что подстроки-палиндромы в ней не изменятся. Итак, если мы найдем самую длинную общую подпоследовательность двух строк до и после переворота, результатом будет подстрока-палиндром.
Объяснение этой проблемы во введении к алгоритму заключается в использовании алгоритма динамического программирования, то есть для всех позиций i в строке S и всех позиций j в S_ мы используем массив dp для записи S и S, оканчивающихся на i и j Наибольший результат общей подпоследовательности, которая может быть образована подстроками _.
Очевидно, что для i=0, j=0 dp[i][j] = 0 (при условии, что строковые индексы начинаются с 1)
Пишем код для DP:
for i in range(1, n):
for j in range(1, m):
if S[i] == S_[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Нетрудно заметить, что сложность этого решения также
. и пространственная сложность тоже
, а это значит, что мы так много работали без какой-либо оптимизации. Так что с этой точки зрения перебор — неплохое решение этой проблемы.
Разбор тут,и он почти такой же.Перейдем сразу к основной теме,лучшему решению этой проблемы,
Алгоритм Манчестера для получения наибольшей подстроки палиндрома за время.
Манчестерский алгоритм
В дополнение к только что упомянутым свойствам у палиндрома есть еще одно свойство, то есть он имеет четность. Короче говоря, длина палиндрома может быть четной или нечетной. Если это нечетное число, то центр палиндрома строки палиндрома является символом, если это четное число, его центр палиндрома фактически находится между двумя символами.
Например:
И ABA, и ABBA являются строками-палиндромами, первая — нечетным палиндромом, а вторая — четным палиндромом.
Эти две ситуации несовместимы, и нам трудно обсудить их вместе.Чтобы упростить задачу, нам нужно сделать предварительную обработку, чтобы превратить все строки-палиндромы в нечетные палиндромы. Как это сделать на самом деле очень просто, вставляем во все два символа специальный символ #.
Например:
abba -> #a#b#b#a#
Таким образом, центр палиндрома становится # в середине. Давайте посмотрим на случай исходного нечетного палиндрома:
aba -> #a#b#a#
Центр палиндрома по-прежнему находится на b, и это по-прежнему нечетный палиндром. Предварительно обработанный код:
def preprocess(text):
new_str = '#'
for c in text:
new_str += c + '#'
return new_str
Манчестерский алгоритм использует три переменные, массивы p, idx и mr. Мы представим их один за другим.
Первый — это массив radis, который содержит радиус самого длинного палиндрома, который может образовать каждая позиция. Обратите внимание, что это не длина, а радиус.
Возьмем пример:
字符串S # a # b # b # a #
radis 1 2 1 2 5 2 1 2 1
Не будем думать о том, как считать этот радиальный массив, а взглянем на его свойства.
Во-первых, радиус палиндрома в позиции i равен radis[i], так какова его длина? Очень просто: radis[2] * 2 - 1. Итак, какова оставшаяся длина этой строки после удаления #? То есть, какова длина до препроцессинга?
Ответ: radis[i] - 1, вычисление тоже очень простое, общая длина равна radis[i] * 2 - 1, где # на единицу больше, чем количество букв, поэтому длина исходной строки равна ( radis[i] * 2 - 1 - 1)/2 = radis[i] - 1.
То есть длина исходной строки связана с массивом radis.
idx хорошо понятен, он относится к нижнему индексу в массиве, и, наконец, mr, который является аббревиатурой most_right. Он записывает самую дальнюю позицию, которую палиндром перед текущей позицией i может расширить вправо.
Это может показаться немного сложным, давайте рассмотрим пример:
В это время i меньше mr, а центр палиндрома, соответствующего mr, равен id. Тогда i находится в диапазоне палиндромов id, для i мы можем получить его симметричное положение относительно id: id * 2 - i, делаем его равным i_. Какой смысл знать это симметричное положение? Очень просто, мы можем быстро определить нижнюю границу radis[i]. К тому времени, когда мы перейдем к i, у нас уже будет результат для i_position. Из результата i_position мы можем вывести диапазон i позиции.
radis[i] >= min(radis[i_], mr-i)
Почему такой результат?
Давайте напишем полный случай, предполагая, что mr-i > radis[i_]. Тогда все палиндромы в позиции i_ попадают в палиндром в позиции id. На данный момент мы можем определить, что radis[i]=radis[i_]. Зачем?
Потому что в соответствии с принципом симметрии, если палиндром с центром в i длиннее, мы предполагаем, что его длина равна radis[i_]+1. Каковы последствия? Если это произойдет, то симметричное положение этой строки относительно id также будет палиндромным в соответствии с симметрией относительно id. Тогда radis[i_1] также должно быть столько-то, что составляет противоречие. Если вы ничего не поняли из текстового описания, давайте рассмотрим следующий пример:
S: c a b c b d b c b a
cradis: x_ i_ 5 i x
В этом примере mr-i=5, radis[i_]=2. Итак, мистер - я > radis[i_]. Если radis[i]=3, то положение x должно быть равно положению id.Точно так же, согласно симметрии, положение x_ также должно быть равно положению id. Тогда radis[i_] также должно быть равно 3. Это противоречит тому, что оно равно 2, поэтому это невозможно, а значение radis[i_] ограничивает возможности положения i, когда mr находится достаточно далеко.
Давайте посмотрим на другую ситуацию, что если mr - i
В этом случае, поскольку mr слишком близко к i, радиус симметричного положения i не может быть расширен в положении i. Но могут быть еще символы справа от mr, могут ли эти символы образовать новый палиндром?
字符串S XXXXXXXXSXXXXXXXXXXXXXXX
radis i_ id i mr
Другими словами, будет ли S[mr+1] находиться в том же положении, что и S[i*2-mr-1]? На самом деле, мы можем знать ответ без осуждения, и ответ будет отрицательным. Посмотрим на картинку:
Согласно симметрии, если положение mr+1 может образовать новую симметрию для i. Поскольку radis[i_] > mr-i, то есть для положения i_, его диапазон симметрии может исходить слева от точки симметрии mr. Мы предполагаем, что буква в этом месте — а, по симметрии мы можем сделать вывод, что позиция mr+1 также должна быть а. Таким образом, эти два a могут образовать новую симметрию, тогда радиус позиции id можно увеличить на 1, что составляет противоречие. Следовательно, в этом случае из-за ограничения mr-i radis[i] может быть равно только mr - i.
При каких обстоятельствах радиус позиции i может продолжать расширяться?
Только когда mr - i == radis[i_], левая часть палиндрома, составленного из id, может не составлять нового палиндрома для i_, но такая возможность существует в правой части.
В приведенном выше примере палиндром положения i_ может продолжаться только до ml влево, потому что положение ml-1 не равно положению, симметричному относительно i_. Для правой части mr он может быть симметричен i без ущерба для корректности raid[id]. В это время мы можем продолжить обход цикла, чтобы расширить палиндром в позиции i.
Хотя анализ всего процесса многогранен и сложен, он не так уж много написан в коде.
# 初始化
idx, mr = 0, 0
# 为了防止超界，设置字符串从1开始
for i in range(1, n):
# 通过对称性直接计算radis[i]
radis[i] = 1 if mr <= i else min(radis[2 * idx - i], mr - i)
# 只有radis[i_] = mr - i的时候才继续往下判断
if radis[2 * idx - i] != mr - i and mr > i:
continue
# 继续往下判断后面的位置
while s[radis[i] + i] == s[i - radis[i]]:
radis[i] += 1
# 更新idx和mr的位置
if radis[i] + i > mr:
mr = radis[i] + i
idx = i
На данный момент реализован манчестерский алгоритм. Несмотря на то, что мы использовали так много места, чтобы представить его, для его написания требуется всего несколько строк кода. Я должен сказать, что это действительно гениально, и может потребоваться много размышлений в первый раз, чтобы действительно понять.
Однако у нас все еще есть проблема, которая не решена: почему такой алгоритм двойного цикла имеет сложность O(n)?
Чтобы понять это, нам нужно отбросить все иллюзии и взглянуть прямо на суть. Хотя мы не знаем, сколько раз будет выполняться цикл, мы можем быть уверены в двух вещах. Через эти две точки мы можем постичь сущность сложности.
Первый пункт, mr увеличивается, он будет только увеличиваться, а не уменьшаться. Второй момент, диапазон mr от 0 до n, а количество раз, которое m увеличивается каждый раз, является количеством петель.
Таким образом, даже если мы не знаем, сколько раз mr менялся и насколько он менялся каждый раз, мы все равно можем быть уверены, что это алгоритм O(n).
На этом содержание статьи закончилось. Если вам понравилось, нажмите и подпишитесь~