Javaで文字列内の最長の回文部分文字列

Longest palindrome substring in a stringは非常に一般的なJava面接の質問です。最長の回文を見つけるには、まずString内でそれを行うためのロジックを特定する必要があります。

String内の最長回文部分文字列のアルゴリズム

ここでのキーポイントは、任意の回文文字列の中央から右と左に1つ移動した場合、常に同じ文字であるということです。例えば、12321では、中央は3で、両側に1つずつ移動し続けると、2、そして1を得ます。このロジックをJavaプログラムで最長の回文を見つけるために使用します。ただし、回文の長さが偶数の場合、中央のサイズも偶数です。したがって、プログラム内でこれも確認する必要があります。例えば、12333321では、中央は33で、両側に1つずつ移動し続けると、3、2、1を得ます。

String内の最長回文部分文字列のJavaプログラム

私たちのJavaプログラムでは、入力文字列を1番目の位置として反復処理し、右と左の文字をチェックします。 パリンドロームの開始位置と終了位置を保存するために、2つのグローバル変数が必要です。 与えられた文字列に複数のパリンドロームがある可能性があるため、すでにより長いパリンドロームが見つかっているかどうかもチェックする必要があります。 すべてのケースで正常に機能する最終プログラムは次のとおりです。

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リポジトリからダウンロードできます。