가장 긴 팰린드롬

• 어렵;
• DP, 투 포인터?
• 디피가 더 이해됨 확장 중심 코드

확장 중심 코드

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    
    int start = 0; // 정답 팰린드롬 시작 인덱스
    int end = 0;   // 정답 팰린드롬 끝 인덱스
    
    for (int i = 0; i < s.length(); i++) {
        // 홀수 길이 팰린드롬 체크
        int len1 = expandFromCenter(s, i, i);
        
        // 짝수 길이 팰린드롬 체크
        int len2 = expandFromCenter(s, i, i + 1);
        
        // 두 길이 중 더 긴 것을 선택
        int len = Math.max(len1, len2);
        
        // 만약 기존에 찾은 팰린드롬보다 길다면 start, end 갱신
        if (len > end - start) {
            // 새로 찾은 팰린드롬의 시작 인덱스 계산
            start = i - (len - 1) / 2;
            // 새로 찾은 팰린드롬의 끝 인덱스 계산
            end = i + len / 2;
        }
    }
    
    // s.substring(a, b)는 b-1까지 포함하므로 end+1
    return s.substring(start, end + 1);
}
 
private int expandFromCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}
 

DP

public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    String res = "";
 
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && (len <= 2 || dp[i+1][j-1])) {
                dp[i][j] = true; // true 면 팰린드롬이라는 의미임.
                if (len > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
    }
    return res;
}