Решение вопроса о кодировании палиндромной подстроки на leetcode. В этом вопросе нас просят найти самую длинную палиндромную подстроку в заданной строке s.
Строка называется строкой-палиндромом, если обратная сторона этой строки совпадает с исходной строкой.
Решение: выполнить один цикл, найти палиндромы нечетной длины, найти палиндромы четной длины и сохранить самый длинный палиндром.
В этом решении мы пройдемся по строке один раз и дважды вызовем функцию, чтобы найти палиндромы четной и нечетной длины и сохранить самый длинный.
Важно отметить, что палиндромы отражают их центр.
Мы хотим начать с постепенного размещения указателя и проверки совпадения левого и правого значений указателя. Если это так, мы посчитаем его палиндромом и увеличим счетчик, чтобы проверить следующий набор значений слева left — count и справа right + count. Например, если мы находим один палиндром, мы увеличиваем счетчик на 1. Затем мы проверяем следующий набор значений слева и справа от указателя, чтобы убедиться, что они также равны. Если значения не совпадают, мы уменьшаем счетчик и возвращаем подстроку с максимальным количеством.
Для палиндрома нечетной длины мы установим центр на i, i, а для палиндрома четной длины мы установим центр на i, i+1
Нам нужно отслеживать самую длинную палиндромную подстроку по мере прохождения строки и обновлять longest всякий раз, когда мы находим большую палиндромную подстроку.
Давайте посмотрим на код:
Пример 1:
Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.
Пример 2:
Input: s = "cbbd" Output: "bb" Explanation: we can find one even length palindrome "bb"
Сложность времени и пространства:
Это решение имеет временную сложность O(n ^ 2) и пространственную сложность O(1). В худшем случае, например, если вся строка является палиндромом, пространственная сложность будет O(n).
