Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 5. Longest Palindromic Substring

HEESOO on Leetcode

👀 문제

https://leetcode.com/problems/longest-palindromic-substring/

👊 도전

1. 설계

  1. P(i,j) (i: 시작 인덱스, j: 종료 인덱스) 가 T이면 P(i+1,j-1)도 T임을 이용한다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public String longestPalindrome(String s) {
        if(s.length()==0 || s==null) return "";
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        int maxSize=0;
        String answer="";
        
        for(int j=0;j<n;j++){// 종료 인덱스
            for(int i=0;i<=j;i++){ // 시작 인덱스
                if(i==j) dp[i][j]=true;//한 자리인 경우
                else if(j==i+1){// 두자리인 경우
                    if(s.charAt(i)==s.charAt(j)) dp[i][j]=true; // 서로 같아야 T
                }
                else{
                    boolean same=s.charAt(i)==s.charAt(j); //i, j가 같은지 체크
                    dp[i][j]=dp[i+1][j-1] && same; //i+1~j-1가 T인지 체크
                }
                
                if(dp[i][j] && j-i+1>maxSize){ // maxSize보다 더 긴 substring을 찾았다면 갱신
                    maxSize=j-i+1;
                    answer=s.substring(i,j+1);
                }
            }
        }
        
        
        return answer;
    }
    
    
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. palindromic 문자열 앞 뒤에 같은 문자열을 추가하면 그것도 palindromic하다
    • i: 시작 인덱스, j: 마지막 인덱스
    • dp[i][j]=dp[i+1][j-1] && s.charAt(i) && s.charAt(j)이어야한다.
    • 만약 문자 하나를 비교하는 경우에는 무조건 T이다(i==j).
    • 문자가 바로 붙어있고 길이가 2인 것은 i, j가 같은 문자인지 확인한다. (j==i+1)
  2. DP를 이용하여 중복 체크를 방지한다
    • 이전에 확인한 적이 있는 곳을 두 번 이상 체크하여 시간 낭비를 방지하기 위해 DP를 사용한다.
  3. 현재 체크한 i~j 문자열이 T이고 길이가 기존 maxSize보다 크다면 갱신한다
    • maxSize: 현재 answer에 저장되어 있는 문자열의 길이
    • answer: 리턴할 문자열
    • j-i+1은 i~j까지의 문자열 길이를 나타낸다.

👏 해결 완료!