Langste Palindroom Substring in een String in Java

Langste palindroomsubstring in een string is een zeer gebruikelijke java sollicitatievraag. Om de langste palindroom in een String te vinden, moeten we allereerst de logica identificeren om dit te doen.

Algoritme voor de langste palindroomsubstring in een string

Het sleutelpunt hier is dat vanuit het midden van elke palindroomstring, als we naar rechts en links gaan met 1 plaats, het altijd hetzelfde karakter is. Bijvoorbeeld 12321, hier is het midden 3 en als we een positie aan beide zijden blijven bewegen, krijgen we 2 en dan 1. We zullen dezelfde logica gebruiken in ons javaprogramma om de langste palindroom te vinden. Als echter de lengte van het palindroom even is, is de grootte van het midden ook even. Dus we moeten ervoor zorgen dat dit ook in ons programma wordt gecontroleerd. Bijvoorbeeld 12333321, hier is het midden 33 en als we een positie aan beide zijden blijven bewegen, krijgen we 3, 2 en 1.

Javaprogramma voor de langste palindroomsubstring in een string

In ons Java-programma zullen we itereren over de invoerstring met mid als eerste plaats en controleren op het juiste en linker teken. We zullen twee globale variabelen hebben om de start- en eindpositie voor een palindroom op te slaan. We moeten ook controleren of er al een langere palindroom is gevonden, aangezien er meerdere palindromen kunnen zijn in de opgegeven string. Hier is het uiteindelijke programma dat goed werkt voor alle gevallen.

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++) {
			// oneven gevallen zoals 121
			String palindrome = intermediatePalindrome(s, i, i);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
			// even gevallen zoals 1221
			palindrome = intermediatePalindrome(s, i, i + 1);
			if (palindrome.length() > longest.length()) {
				longest = palindrome;
			}
		}
		return longest;
	}

}

Hieronder staat een afbeelding die de uitvoer van het bovenstaande langste palindroom Java-programma laat zien. We kunnen de bovenstaande code verbeteren door de controle op palindromen en lengte van het langste palindroom in een andere functie te plaatsen. Ik heb echter dat deel aan jou overgelaten. 🙂 Laat me alsjeblieft weten als er andere betere implementaties zijn of als het ergens niet lukt.

Je kunt het volledige voorbeeldcode downloaden vanuit onze GitHub Repository.