在Java中字符串中的最长回文子串

最长回文子串在字符串中是一个非常常见的Java面试问题。要找出字符串中的最长回文子串，首先，我们需要确定解决此问题的逻辑。

字符串中的最长回文子串算法

这里的关键点是，从任何回文字符串的中间开始，如果我们向右和向左移动一个位置，始终是相同的字符。例如，12321，在这里中间是3，如果我们在两边继续移动一个位置，我们得到2，然后是1。我们将在我们的Java程序中使用相同的逻辑来找出最长的回文子串。但是，如果回文长度是偶数，中间大小也是偶数。因此，在我们的程序中，我们需要确保也检查了这一点。例如，12333321，在这里中间是33，如果我们在两边继续移动一个位置，我们得到3、2和1。

字符串中的最长回文子串Java程序

在我们的Java程序中，我们将遍历输入字符串，以中间位置为第一个位置，并检查右边和左边的字符。我们将有两个全局变量来保存回文的起始和结束位置。我们还需要检查是否已经找到了更长的回文，因为在给定的字符串中可能存在多个回文。以下是适用于所有情况的最终程序。

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++) {
			//奇数情况，如121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			//偶数情况，如1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

下面的图像显示了上述最长回文Java程序的输出。通过将回文和最长长度的检查移到不同的函数中，我们可以改进上述代码。然而，我把这部分留给你了。 🙂 如果有任何其他更好的实现或在任何情况下失败，请告诉我。

您可以从我们的GitHub存储库下载完整的示例代码。