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 存儲庫下載完整的示例代碼。