Lv.3 가장 긴 팰린드롬

https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

팰린드롬은 항상 대칭이다.

양끝이 같을 때, 그 사이가 이미 대칭인 경우는 전체도 대칭이라는 전제를 가지고

길이가 짧은 부분 문자열부터 시작하여 긴 부분 문자열까지

한번 팰린드롬인지를 확인했던 구간의 결과를 저장해놓고

해당 구간의 결과를 참조하면서 풀면되지만...

 

슬프게도 전자의 방법보다는 Manacher 알고리즘이라는

특정 알고리즘을 사용하는 방법이 더 효율적이라고 한다.

 

첫번째 풀이: Botom Up DP - 가장 직관적이라 구현이 용이하다.

두번째 풀이: Top Down DP - 긴 문자열부터 확인해서 팰린드롬을 발견하는 즉시 종료하므로 처리 속도가 조금 더 빠르다.

// Bottom Up DP
class Solution {
    public int solution(String s) {
        int max = 1; // s의 길이는 최소 1이상이고 문자열의 길이가 1인 경우 항상 팰린드롬이므로 1로 초기화 한다.
        boolean[][] dp = new boolean[s.length()][s.length()]; // dp[i][j] = 인덱스 i ~ j 까지의 부분 문자열이 팰린드롬인지 여부
        
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true; // 문자 하나만 있는 경우 항상 팰린드롬이므로 i ~ i 구간은 팰린드롬이다.
        }
        for (int i = 0; i < s.length() - 1; i++) {
            char left = s.charAt(i);
            char right = s.charAt(i + 1);
            if (left == right) { // 앞뒤 문자가 같으면 항상 팰린드롬이므로
                dp[i][i + 1] = true; // i ~ i + 1 구간은 팰린드롬이다.
                max = 2; // 길이가 2인 팰린드롬을 찾았으므로 2를 저장한다.
            }
        }
        for (int i = 2; i < s.length(); i++) { // 길이가 3인 부분 문자열 ~ 길이가 s.length()(전체 문자열)인 문자열까지 반복하며 확인
            for (int j = 0; j < s.length() - i; j++) { // 길이가 i + 1인 모든 부분 문자열을 확인한다.
                char left = s.charAt(j); // 왼쪽 끝 문자
                char right = s.charAt(j + i); // 오른쪽 끝 문자
                if (left != right || !dp[j + 1][j + i - 1]) { // 들여쓰기가 3번이상 발생하는 경우를 지양하기에(주관적인 생각이다.)
                    continue; // 밑 줄의 조건식을 뒤집어서 넘겼다.(오히려 가독성이 떨어질 수 있다는 점은 주의해야 한다.)
                } // 양 끝 문자가 같을 때 && 그 사이의 문자열이 팰린드롬(대칭)이면 팰린드롬(대칭)이다.
                dp[j][j + i] = true; // j ~ j + i 구간은 팰린드롬이다.
                max = i + 1; // 길이가 i + 1인 팰린드롬을 찾았으므로 i + 1을 저장한다.
            }
        }
        
        return max; // 짧은 부분 문자열부터 시작했으므로 저장되어 있는(가장 마지막에 저장된) 값이 곧 가장 긴 팰린드롬의 길이다.
    }
}

// Top Down DP
class Solution {
    static int max;

    public int solution(String s) {
        int[][] dp = new int[s.length()][s.length()];
        
        for (int i = s.length() - 1; i >= 0; i--) {
            if (max >= i + 1) {
                break;
            }
            for (int j = 0; j < s.length() - i; j++) {
                int left = j;
                int right = j + i;
                recursive(dp, s, left, right);
            }
        }
        
        return max;
    }
    
    static int recursive(int[][] dp, String s, int left, int right) {
        if (dp[left][right] != 0) {
            return dp[left][right];
        }
        if (left == right || left - right == 1) {
            max = left - right + 1;
            return dp[left][right] = 1;
        }
        if (s.charAt(left) == s.charAt(right)) {
            int result  = recursive(dp, s, left + 1, right - 1);
            if (result == 1) {
                max = right - left + 1;
                return dp[left][right] = 1;
            }
        }
        return dp[left][right] = -1;
    }
}