[Leetcode] 5. Longest Palindromic Substring

Identifying the Problem

string 문자열 내에서 가장 긴 Palindromic(좌우 대칭)인 문자열을 구한다.

Organizing thoughts

#1은 내가 생각한 풀이 , #2는 다른 사람의 코드를 해설하였다.

 

#1 window slicing으로 window 크기를 s.size 에서 점점 줄여나가면서 판단한다.

window에 해당하는 string과 뒤집은 string이 동일한지 판단한다.
reverse 사용 한다면 O(n²)로 보이겠지만, 실제로는 O(n³)이다.

#2 가능한 모든 substring을 확인하고, 가장 긴 substing을 찾기
양파 까는 것처럼 양끝이 같으면, 그 안쪽도 같은지, 그 안쪽도 같으면 그 안쪽도 같은지
dp로 확인한다.

Sourcecode

## 내 풀이 (역시나 time limit이 뜬다.)

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if(s.size() == 1) return s;
        int win_size = s.size();
        int i = 0;
        
        while(win_size >= 2)
        {
            i = 0;
            while(i + win_size - 1 < s.size())
            {
                string tmp = s.substr(i,win_size);
                reverse(tmp.begin(), tmp.end());

                if(tmp == s.substr(i,win_size))
                    return s.substr(i,win_size);
                i++;
            }
            win_size -=1;
        }
        return s.substr(0,1);
    }
};

## 정답 풀이 및 출처

https://leetcode.com/problems/longest-palindromic-substring/discuss/1273319/C%2B%2B-2D-dp-solution

핵심은 left와 right가 같다면, 그 안쪽도 같은지 계속 들어가는 것이다.
1. left right index가 같은 경우 palindromic 이므로 초기값 true
2. 가능한 모든 substring을 최소 단위부터 탐색한다.
3. left와 right의 index의 글자가 같은 경우 left 다음 right 이전의 문자도 동일한지 확인

ex : bab 라면 a는 1. 에서 palindromic 확인했으므로 bb 일 때 이전과 같은지 확인

ex : baab 라면 aa는 2. 에서 palindromic 확인했으므로 bb 일 때 이전과 같은지 확인
4. palindromic 인 경우 가장 긴 substring의 길이와 start 위치 저장

 

표를 자세히 보면 true 인 곳을 중심으로, 대각선 오른쪽 위에 정답이 있음을 확인할 수 있다.

이런 식으로 true가 가장 많이 연결된 dp를 찾으면 된다.

left / right	b	a	b	a	d
b	true , len = 1	false	true , len = 3	false	false
a	x	true , len = 1	false	true , len = 3	false
b	x	x	true , len = 1	false	false
a	x	x	x	true , len = 1	false
d	x	x	x	x	true , len = 1

class Solution {
public:
    
    string longestPalindrome(string s) {
        int len = s.length();
        bool dp[len][len]; 
        
        if(s.length()==1)
            return s;
        
        int start = 0; int long_len = 1;
        
        for(int i=0; i<s.length(); i++)
            dp[i][i] = 1;
        
        for(int i = len-1; i>=0; i--)
        {
            for(int dist = 1; dist<len-i; dist++)
            {
                int j = dist + i;
                dp[i][j]= (dist==1)? s[i]==s[j] : (s[i]==s[j] && dp[i+1][j-1]);
                if(dp[i][j] && j-i+1 >long_len)
                {    
                    long_len = j-i+1;
                    start = i;
                }
            }
        }
        return s.substr(start, long_len);
    }
};