Längster Palindrom-Teilstring in einem String in Java

Die längste Palindrom-Teilfolge in einem String ist eine sehr häufige Java-Interview-Frage. Um das längste Palindrom in einem String zu finden, müssen wir zunächst die Logik dazu identifizieren.

Algorithmus für die längste Palindrom-Teilfolge in einem String

Der Schlüsselpunkt hierbei ist, dass von der Mitte jeder Palindrom-Teilfolge aus, wenn wir um 1 Platz nach rechts und links gehen, es immer dasselbe Zeichen ist. Zum Beispiel 12321, hier ist die Mitte 3, und wenn wir uns auf beiden Seiten um eine Position bewegen, erhalten wir 2 und dann 1. Wir werden dieselbe Logik in unserem Java-Programm verwenden, um das längste Palindrom zu finden. Wenn jedoch die Länge des Palindroms gerade ist, ist die Mitte ebenfalls gerade. Daher müssen wir in unserem Programm sicherstellen, dass dies ebenfalls überprüft wird. Zum Beispiel 12333321, hier ist die Mitte 33, und wenn wir uns auf beiden Seiten um eine Position bewegen, erhalten wir 3, 2 und 1.

Java-Programm für die längste Palindrom-Teilfolge in einem String

In unserem Java-Programm werden wir über den Eingabestring iterieren, wobei ‚mid‘ die erste Position ist, und das rechte und linke Zeichen überprüfen. Wir werden zwei globale Variablen haben, um die Start- und Endposition für Palindrome zu speichern. Wir müssen auch überprüfen, ob bereits ein längeres Palindrom gefunden wurde, da es mehrere Palindrome im gegebenen String geben kann. Hier ist das endgültige Programm, das für alle Fälle gut funktioniert.

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++) {
			// ungerade Fälle wie 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			// gerade Fälle wie 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

Das folgende Bild zeigt die Ausgabe des oben genannten längsten Palindrom-Java-Programms. Wir können den obigen Code verbessern, indem wir die Überprüfung auf Palindrome und die längsten Längen in eine separate Funktion verschieben. Diesen Teil habe ich jedoch für dich stehen gelassen. 🙂 Bitte lassen Sie mich wissen, ob es bessere Implementierungen gibt oder ob es in irgendeinem Fall fehlschlägt.

Sie können den vollständigen Beispielcode von unserem GitHub-Repository herunterladen.