[Java] LeetCode 5번 Longest Palindromic Substring

[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); } }

반응형

from http://blue-jay.tistory.com/69 by ccl(A) rewrite - 2021-09-25 21:01:36