Задача.
Дана строка. Нужно найти самую длинную подстроку, которая является палиндромом.
Например,
Для "babad", ответ "bab" или "aba"
Для "cbbd", ответ "bb"
Для "abaxyzzyxb", ответ "xyzzyx".
Ссылка на leetcode: https://leetcode.com/problems/longest-palindromic-substring/
Решение.
Рассмотрим на примере строки "abaxyzzyxb":
В ней есть множество подстрок, которые являются палиндромами. Если не брать в расчет тривиальные палиндромы, состоящие из одного символа, то она содержит еще четыре нетривиальные подстроки, которые являются палиндромами.
Самый длинный из которых это xyzzyx.
Я уже публиковал решение задачи на проверку того, является ли строка палиндромом или нет: Проверка на палиндром
Если кратко, то мы используем подход Two Pointers (два указателя). Используем два указателя. Один указывает на начало строки, а второй на конец. Если символы, на которые они указывают не равны - то строка не палиндром. Если равны - сдвигаем указатели в направлении к середине строки (левый указатель сдвигаем вправо, а правый сдвигаем влево).
boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
Эта проверка работает за O(n).
Чтобы решить исходную задачу - мы можем сгенерировать все возможные подстроки и проверить, не являются ли они палиндромами и выбрать среди них самый длинный.
Это можно сделать так:
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if (isPalindrome(s, i, j)) {
....
}
}
}
Такой алгоритм работает за O(n^3), т.к. у нас два вложенных цикла и внутри еще проверка на палиндром.
Полный код решения:
class Solution {
public String longestPalindrome(String s) {
int maxLen = 0;
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if (isPalindrome(s, i, j)) {
int len = j - i + 1;
if (len > maxLen) {
maxLen = len;
start = i;
end = j;
}
}
}
}
return s.substring(start, end + 1);
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
Time Complexity O(n^3), Space Complexity O(1).
Можно ли улучшить это решение? Да, можно.
Для этого нам, каким-то образом, надо избавиться от одного из вложенных циклов.
Проверка на палиндром в любом случае будет работать за O(n). От этого не избавиться. Т.е. нужно как-то, всего лишь один раз пройтись по строке, а не двумя вложенными циклами.
Нам нужны эти два вложенных цикла, чтобы задать начало и конец подстроки, которую мы проверяем. Но мы можем переосмыслить этот подход.
Для этого можно изменить подход в определении того, что строка является палинромом или нет. Мы можем вместо того, чтобы задавать начало и конец подстроки для проверки, задавать только лишь центр подстроки и при проверке на палиндром идти от центра к краям.
Например, если мы рассматриваем строку "abaxyzzyxb". Одном из потенциальных центров палидромической подстроки является промежуток между буквами z.
Задав этот центр, мы может идти от него к краям и проверять, является ли текущая подстрока палиндромом или нет. По итерациям это выглядит так:
В коде такую проверку можно реализовать следующим образом (от центра к краям). В качестве результата вернем индексы максимального палиндрома начинающегося в заданном центре (вначале left и right указывают на один и тот же символ/центр или на соседнии, если центр это промежуток между символами):
private int[] getPalindromeStartAndEndIndexes(String s, int left, int right) {
while (left >= 0 && right < s.length()) {
if (s.charAt(left) != s.charAt(right)) {
break;
}
left--;
right++;
}
return new int[] {left + 1, right - 1};
}
Хорошо, мы избавились от необходимости задания начала и конца подстрок. Нам нужно в цикле пройтись по всем потенциальным центрам палиндромов. Тут важно заметить, что для палиндромов нечетной длинны, центр это конкретный символ. А для четной - это промежуток между символами.
Вначале, центр потенциального палиндрома это первый символ строки и начальные значения left и right равны и указывают на этот первый символ:
Далее в проверке на палиндром мы будем расширяться влево и вправо от этого центра и найдем максимальный палиндром, центр которого это первый символ.
Далее мы перейдем к новому потенциальному центру - промежутку между певым и вторым символом:
После проверки всех палиндромов, центр которых это промежуток между первым и вторым символом, перейдем к следующему потенциальному центру - второму символу строки и т.д.
В коде это будет выглядеть так:
class Solution {
public String longestPalindrome(String s) {
int maxLen = 0;
int start = 0;
int end = 0;
for (int center = 0; center < s.length() * 2; center++) {
int left = 0;
int right = 0;
if (center % 2 == 0) {
left = center / 2;
right = left;
} else {
left = center / 2;
right = left + 1;
}
int[] startAndEndIndexes = getPalindromeStartAndEndIndexes(s, left, right);
int currentStart = startAndEndIndexes[0];
int currentEnd = startAndEndIndexes[1];
int len = currentEnd - currentStart + 1;
if (len > maxLen) {
maxLen = len;
start = currentStart;
end = currentEnd;
}
}
return s.substring(start, end + 1);
}
private int[] getPalindromeStartAndEndIndexes(String s, int left, int right) {
while (left >= 0 && right < s.length()) {
if (s.charAt(left) != s.charAt(right)) {
break;
}
left--;
right++;
}
return new int[] {left + 1, right - 1};
}
}
Это решение работает за O(n^2). Space complexity O(1).
Top comments (0)