Самая длинная подстрока палиндрома в строке в Java
Самая длинная подстрока палиндрома в строке — это очень распространенная строка, прежде всего нам нужно определить логику для этого.
Самая длинная палиндромная подстрока в строковом алгоритме
Ключевым моментом здесь является то, что от середины любой палиндромной строки, если мы идем вправо и влево на 1 позицию, это всегда один и тот же символ. Например, 12321, здесь mid равно 3, и если мы продолжим перемещаться на одну позицию в обе стороны, мы получим 2, а затем 1. Мы будем использовать ту же логику в нашей Java-программе, чтобы найти самый длинный палиндром. Однако если длина палиндрома четная, то средний размер тоже четный. Поэтому нам нужно убедиться, что в нашей программе это тоже проверяется. Например, 12333321, здесь mid равно 33, и если мы будем двигаться на одну позицию в обе стороны, мы получим 3, 2 и 1.
Самая длинная подстрока палиндрома в программе String Java
В нашей Java-программе мы будем перебирать входную строку с mid как 1-е место и проверять правый и левый символы. У нас будет две глобальные переменные для сохранения начальной и конечной позиции палиндрома. Нам также нужно проверить, не найден ли уже более длинный палиндром, поскольку в данной строке может быть несколько палиндромов. Вот окончательная программа, которая отлично работает во всех случаях.
package com.journaldev.util;
public class LongestPalindromeFinder {
public static void main(String[] args) {
System.out.println(longestPalindromeString("1234"));
System.out.println(longestPalindromeString("12321"));
System.out.println(longestPalindromeString("9912321456"));
System.out.println(longestPalindromeString("9912333321456"));
System.out.println(longestPalindromeString("12145445499"));
System.out.println(longestPalindromeString("1223213"));
System.out.println(longestPalindromeString("abb"));
}
static public String intermediatePalindrome(String s, int left, int right) {
if (left > right) return null;
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
// O(n^2)
public static String longestPalindromeString(String s) {
if (s == null) return null;
String longest = s.substring(0, 1);
for (int i = 0; i < s.length() - 1; i++) {
//odd cases like 121
String palindrome = intermediatePalindrome(s, i, i);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
//even cases like 1221
palindrome = intermediatePalindrome(s, i, i + 1);
if (palindrome.length() > longest.length()) {
longest = palindrome;
}
}
return longest;
}
}
Вы можете загрузить полный пример кода из нашего репозитория GitHub.