[Programmers] 가장 긴 팰린드롬 (JAVA)

프로그래머스

 

풀이

 

[자바 알고리즘 인터뷰] 6장 문자열 처리(6) 가장 긴 팰린드롬 부분 문자열

요 게시물에서 힌트를 많이 얻었습니다.

 

홀수/짝수로 체크를 해야하는 이유에 대해 생각하지 못했는데,

abba일 경우 홀수로만 체크하게 되면 팰린드롬이 될 수 없기 때문에 짝수로 체크해줘야 합니다.

 

투 포인터(Tow Pointers)가 팰린드롬을 발견하면 확장하는 형태로 문제를 풀어줬다.

투포인터로 팰린드롬을 찾은 뒤에, left--와 right++를 통해 좌우로 확장해가며 가장 긴 팰린드롬을 찾아줬다.

 

전체코드

import java.io.*;
import java.util.*;

class Solution
{
    static char word[];
    static int max = 0;
    public int solution(String s)
    {
        int answer = 0;
        
        word = s.toCharArray();

        for(int i=0; i<s.length(); i++){
            checkPalindrome(i, i+2);
            checkPalindrome(i, i+1);
        }
        return max;
    }
    static void checkPalindrome(int left, int right){
        while(left >=0 && right < word.length && word[left] == word[right]){
            left--;
            right++;
        }
        
        if(max < right-left-1){
            max = right-left-1;
        }
    }
}