הפלינדרום הארוך ביותר במחרוזת בשפת ג'אווה

התת-מחרוזת הפאלינדרום הארוכה ביותר במחרוזת היא שאלת ראיון מקובץ אחד java. כדי למצוא את הפאלינדרום הארוך ביותר בתת-מחרוזת מחרוזת, יש צורך תחילה לזהות את הלוגיקה לביצוע זאת.

אלגוריתם למציאת הפאלינדרום הארוך ביותר במחרוזת

הנקודה המרכזית כאן היא שמהאמצע של כל מחרוזת פאלינדרום אם נעבור ימינה ושמאלה במקום אחת, תמיד נקבל את אותה התו. לדוגמה 12321, כאן המרכז הוא 3 ואם נמשיך להזיז מקום אחד בשני הצדדים, נקבל 2 ואז 1. נשתמש באותה הלוגיקה בתוכנית ה-Java שלנו כדי למצוא את הפאלינדרום הארוך ביותר. אולם, אם אורך הפאלינדרום הוא זוגי, אורך המרכז גם הוא זוגי. לכן יש צורך לוודא בתוכנית שלנו שגם זאת נבדקת. לדוגמה, 12333321, כאן המרכז הוא 33 ואם נמשיך להזיז מקום אחד בשני הצדדים, נקבל 3, 2 ואז 1.

תוכנית 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;
	}

}

התמונה למטה מראה את תוצאות תוכנית הפלינדרום הארוכה ביותר בג'אווה שלמעלה. ניתן לשפר את הקוד למעלה על ידי העברת בדיקת הפלינדרום והאורך הארוך לתוך פונקציה שונה. עם זאת, השארתי את החלק הזה לך. 🙂 אני כאן אם יש יישורים טובים נוספים או אם יש כשלונות באיזשהו מקרה.

ניתן להוריד את קוד הדוגמה המלא ממערכת הניהול שלנו ב-GitHub.