자바에서 문자열의 가장 긴 팰린드롬 부분 문자열

가장 긴 팰린드롬 부분 문자열은 매우 일반적인 자바 인터뷰 질문입니다. 문자열에서 가장 긴 팰린드롬을 찾으려면 먼저 그것을 수행하는 논리를 식별해야합니다.

문자열에서 가장 긴 팰린드롬 부분 문자열 알고리즘

여기서의 핵심은 팰린드롬 문자열의 중간부터 오른쪽과 왼쪽으로 1자리씩 이동할 때 항상 동일한 문자임을 의미합니다. 예를 들어 12321에서 중간은 3이고 양쪽으로 한 자리씩 이동하면 2와 1이됩니다. 우리는 자바 프로그램에서도 동일한 논리를 사용하여 가장 긴 팰린드롬을 찾을 것입니다. 그러나 팰린드롬 길이가 짝수인 경우 중간 크기도 짝수입니다. 따라서 우리의 프로그램에서도 이를 확인해야합니다. 예를 들어 12333321에서 중간은 33이고 양쪽으로 한 자리씩 이동하면 3, 2, 1이됩니다.

문자열에서 가장 긴 팰린드롬 부분 문자열 자바 프로그램

우리의 자바 프로그램에서는 중간을 첫 번째 위치로 설정하고 오른쪽과 왼쪽 문자를 확인하기 위해 입력 문자열을 반복합니다. 팰린드롬의 시작 위치와 끝 위치를 저장하기 위해 두 개의 전역 변수가 필요합니다. 또한 주어진 문자열에 여러 개의 팰린드롬이 있을 수 있으므로 이미 더 긴 팰린드롬이 발견되었는지를 확인해야 합니다. 모든 경우에 잘 작동하는 최종 프로그램은 다음과 같습니다.

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 저장소에서 다운로드할 수 있습니다.