[Java] LeetCode 5번 Longest Palindromic Substring

dp[start][end]에 start부터 end까지의 부분 문자열이 팔린드롬인지 여부를 저장하였다. 1이면 팔린드롬이고 0이면 아직 체크되지 않은 값이며, -1이면 팔린드롬이 아니다. 

이중 포문을 돌면서 i와 j를 시작과 끝으로 하는 문자열이 팔린드롬인지 아닌지를 체크하였다. 이미 체크한 문자열들을 다시 검사하지 않기 위해서 dp를 사용하였으며 O(n^2) 보다는 조금 더 느린 풀이이지만 통과되었다.

class Solution {
    public int checkPalindrome(int[][] dp, int start, int end, String s) {
        if (dp[start][end] != 0) {
            return dp[start][end];
        }
        int len = end - start + 1;
        if (len <= 1) {
            dp[start][end] = 1;
        } else if (s.charAt(end) == s.charAt(start)) {
            dp[start][end] = checkPalindrome(dp, start + 1, end - 1, s);
        } else {
            dp[start][end] = -1;
        }
        return dp[start][end];
    }

    public String longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                int len = j - i + 1;
                if (len > maxLen && checkPalindrome(dp, i, j, s) == 1) {
                    maxLen = len;
                    start = i;
                    end = j + 1;
                }
            }
        }
        return s.substring(start, end);
    }
}