Java) Leetcode 5. Longest Palindromic Substring (DP 풀이)

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
 

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

 

 

문제 : 

문자열 s 가 주어졌을때, 문자열 안에서 가장 긴 팰린드롬을 substring하여 리턴하는 문제이다.

 

이 문제를 해결하기 위해 브루트포스를 이용하여 푸는것도 가능하지만 이번에는 동적 프로그래밍(DP)를 이용해 보기로 헀다.

 

풀이 :

 

1. 우선 문자열 s의 길이가 0일 경우 팰린드롬이

아니고 1이면 자동적으로 팰린드롬이 완성이 된다. 

예) s = "a"; 

문자열이 한글자일 경우 좌에서 보나 우에서 보나 일치하기에 팰린드롬이다.  

    int n = s.length(); // s의 길이 저장
    if(n<=1){ // 0 혹은 1이면 s 반환
        return s;
    }

 

 

2. 가장 긴 팰린드롬을 s에서 추출(substring)해야 하기에 

최대 길이를 저장할 maxLen와 

substring을 위한 인덱스 start, end를 선언했다.

이미 문자열 길이가 1이하인 경우는 제외시켰기에 최대 길이는 1부터 시작하므로 maxLen=1로 초기화 하였다.

     int maxLen = 1; // 최대 길이 저장
     int start =0;   // s.substring(start,  시작 인덱스
     int end = 0;    // end);               끝 인덱스

 

 

이제 마지막으로 동적 프로그래밍에 사용할 배열을 선언한다.

 

boolean[][] dp = new boolean[n][n];

 

 

3. 배열을 boolean으로 선언한 이유는 문자열 s에서 발생할 수 있는 모든 경우의 수 중에서 팰린드롬인 경우를 표기하기 위함이다.

 

배열이 n * n (문자열 길이 * 문자열 길이)인 이유는 다음과 같다.

만약 주어진 문자열이 "babad"일 때 2차원 배열 dp에서 표기할 수 있는 문자열 s의 조합이다.

  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

 

 

4. 이제 문자열 s의 모든 조합을 확인하기 위하여 for문을 사용해 문자열을 탐색하겠다.

 

     for(int i=0; i<n;i++){ // 첫번째 for 문
     	dp[i][i] = true; // 인덱스의 위치가 같은 곳을 true로
        for(int j=0;j<i;j++){ // 두번재 for 문
        }
     }

 

i==j 일때 팰린드롬이 형성됨으로 dp 배열에서 dp[i][i] 을 true로 만들어준다.

예) 

i =0, j =0    // 비교하는 두 인덱스의 요소의 위치가 같을 때

s[0] == s[0]   // badad의 0번 인덱스는 b==b 이다.

dp[0][0]       // 고로 i==j 는 i==i와 같고 dp[i][i]는 팰린드롬이므로 전부 true

 

  j →   0   1   2   3   4
     ---------------------
i=0 |   b  
i=1 |       a  
i=2 |           b   
i=3 |               a   
i=4 |                   d


  j →   0   1   2   3   4
     ---------------------
i=0 |   T  
i=1 |       T  
i=2 |           T   
i=3 |               T   
i=4 |                   T

 

 

밑준비는 끝났으니 이제 팰린드롬인지 판단하는 조건을 쓰겠다.

조건은 다음과 같다 :

 if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){

 

 

• s[j] == s[i]: 양 끝 문자가 같고
• i - j <= 2: 길이가 3이하인 경우는 바로 확인 가능  (i = 2; j= 0 일때 배열에선 0,1,2 니까 길이가 3이다. 예 bab)
• 그 외는 내부 문자열 dp[j+1][i-1]이 팰린드롬인지 확인

1. s.charAt(j) == s.charAt(i)

→ 먼저 양 끝 문자가 같아야 팰린드롬일 가능성이 생긴다.
예: "a**bab**a"에서 양쪽 a가 같아야 팰린드롬일 가능성이 있다..

 

2. dp[j + 1][i - 1] == true

→ 가운데 문자열 s[j+1..i-1]이 이미 팰린드롬이어야 전체도 팰린드롬이다.

예를 들어:

 j가 0, i= 4

• 전체 문자열: s[0..4] = "ababa"
• 양끝 같음: s[0] == s[4] == 'a'
• 중간 부분: s[1..3] = "bab" → 이게 팰린드롬이어야 "ababa"도 팰린드롬

조금 이해가 안간다면 이렇게 설명할 수 있다. 

i = 1

• j = 0 → s[0]="b", s[1]="a" → 다름 → dp[0][1]=false

i = 2

• j = 0 → s[0]="b", s[2]="b", 길이=3 → 가운데 "a"는 팰린드롬 (dp[1][1]=true) → dp[0][2] = true
• j = 1 → s[1]="a", s[2]="b" → 다름 → dp[1][2] = false

➡ "bab" 팰린드롬 발견!

i = 3

• j = 0 → s[0]="b", s[3]="a" → 다름
• j = 1 → s[1]="a", s[3]="a", 길이=3 → 가운데 "b"는 팰린드롬 (dp[2][2]=true) → dp[1][3]=true
• j = 2 → s[2]="b", s[3]="a" → 다름

➡ "aba" 팰린드롬 발견 (같은 길이)

i = 4

• j = 0~3 → 모두 양 끝 문자 다름 → dp[j][4] = false 전부

---

 

팰린드롬일 가능성이 있는 인덱스들을 찾았다면 이어서 그것을 dp에 체크한다.

그리고 두 인덱스 사이의 길이가 maxLen보다 클 경우 maxLen를 갱신하고

start와 end 좌표도 갱신한다.

 

dp[j][i] = true;
if(i-j+1>maxLen){
    maxLen = i-j+1;
    start = j;
    end = i;
}

 

완성된 for문은 다음과 같다.

 

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     }

 

 

모든 순회를 끝나면 DP는 이렇게 생긴다.

 

  j →   0   1   2   3   4
     ---------------------
i=0 |   T   F   T   F   F  = bab
i=1 |       T   F   T   F  = aba
i=2 |           T   F   F
i=3 |               T   F
i=4 |                   F



  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d 
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

 

이제 마지막으로 구한 두  인덱스를 사용하여 문자열 s 안의 가장 긴 팰린드롬을 리턴하면 끝이다.

 

class Solution {
    public String longestPalindrome(String s) {
     int n = s.length();
    if(n<=1){
        return s;
    }
     int maxLen = 1;
     int start =0;
     int end = 0;

     boolean[][] dp = new boolean[n][n];

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     } 

     return s.substring(start,end+1); 
    }
}