Вчера был 63-й день моего кодинга. Я решил один вопрос.
Задача: Самый длинный палиндром в строке
Для заданной строки S найдите самую длинную палиндромную подстроку в S.Подстрока строки S: S[ i . . . . j ] где 0 ≤ i ≤ j ‹ len(S). Строка-палиндром: строка, которая читается так же в обратном порядке. Более формально, S является палиндромом, если reverse(S) = S.В случае конфликта вернуть подстроку, которая встречается первой (с наименьшим начальным индексом).
Пример 1:
Input: S = "aaaabbaa" Output: aabbaa Explanation: The longest Palindromic substring is "aabbaa".
Пример 2:
Input: S = "abc" Output: a Explanation: "a", "b" and "c" are the longest palindromes with same length. The result is the one with the least starting index.
Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию longestPalin(), которая принимает строку S в качестве входных данных и возвращает самую длинную палиндромную подстроку S.
Ожидаемая временная сложность:O(|S|2).
Ожидаемое вспомогательное пространство:O(1).
Решение (в Java)
- Пройдите по строке и считайте каждый индекс средней точкой строки-палиндрома. Здесь будут встречаться два различных случая.
- Случай 1: палиндромная строка имеет четную длину
- В этом случае назначьте два указателя left = i — 1 и right = i в качестве центра и разверните влево и вправо в обоих направлениях, пока s[left] == s[right]. Продолжайте обновлять начальный индекс и максимальную длину палиндромной строки.
- Случай 2: палиндромная строка имеет нечетную длину
- В этом случае два указателя будут назначены как левый = i -1 и правый = i + 1, поскольку индекс i является средним элементом. Теперь повторите тот же процесс, что и для строки четной длины.
- Возвращает палиндромную подстроку максимальной длины.
class Solution{ static String longestPalin(String S){ int start=0, end=1; for(int i=1; i<S.length(); i++){ int left=i-1; int right=i; while(left>=0 && right<S.length() && S.charAt(left)==S.charAt(right)){ if(right-left+1>end){ start=left; end= right- left+1; } left--; right++; } left=i-1; right=i+1; while(left>=0 && right<S.length() && S.charAt(left)==S.charAt(right)){ if(right-left+1>end){ start=left; end= right- left+1; } left--; right++; } } String ans=""; for( int i=start; i<start+end; i++){ ans+=S.charAt(i); } return ans; } }