[Dynamic Programming][Medium] 5. Longest Palindromic Substring

 

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

 

Q. 주어진 string s의 가장 긴 palindrome이 되는 sub string 을 찾아라. 

 

Solution. 

 우선 직관적으로 생각해 보자. 

 string에서 시작점과 끝점을 정하고 해당 sub string이 palindrom이 되는지 체크한다. 

 직관적이다. 

 코드로 옮겨 보자. 

 

 

    bool IsPalindrome(string& s)
    {
        for(int q = 0; q < s.size()/2; ++q)
        {
            if(s[q] != s[ s.size()-1-q ])
                return false;
        }
        return true;
    }
public:
    string longestPalindrome(string s) 
    {
        string sRet = "";
        for(int left = 0; left < s.size(); ++left)
        {
            for(int right = left; right < s.size(); ++right)
            {
                string cur = s.substr(left, right-left+1);
                if(IsPalindrome(cur))
                {
                    if(sRet.size() < cur.size())
                        sRet = cur;
                }
            }
        }
        return sRet;
    }

 

일단 매번 sub str을 하는 것을 차치하고라도, 최악의 경우 TC 가 O(N^3) 이 나올 가능성이 있으므로, 옳지 않아 보인다. 

로직 접근에 대한 최적화가 필요하다.

 

 

Palindrom check에 looping이 필요하다. 이는 필수이다. 

string에서 substring을 얻으려면 시작과 끝이 필요하다. 따라서 2중 loop가 필요하다. 

이 조건을 다시 한번 생각해 보자. 

현재 필요한 sub string은 모든 sub string이 아니고, 특별한 sub string이 필요하다. 

palindrom한 sub string이 필요하다. 

따라서 여기서, 시작과 끝을 얻어 sub string을 얻는 대신, 

sub string의 중심에서 최대 palindrom을 체크하는 전략으로 접근 방향을 변경한다. 

그러면 sub string을 얻는데에 단일 loop만 필요할 것이다. 

 

이 전략대로 로직을 수정하고 다시 코드를 작성해 본다. 

 

    string longestPalindrome_helper(string& s, int left, int right)
    {
        string subPal = "";
        if (left < 0 || right >= s.size())
            return subPal;

        while (true)
        {
            if (left < 0 || right >= s.size() || s.at(left) != s.at(right))
            {
                ++left; --right;
                subPal = s.substr(left, right - left + 1);
                break;
            }
            ++right;
            --left;
        }
        return subPal;
    }
public:
    string longestPalindrome(string s) 
    {
        string maxPal = "";
        for (int k = 0; k < s.size(); ++k)
        {
            string evenPal = longestPalindrome_helper(s, k, k + 1);
            string oddPal = longestPalindrome_helper(s, k, k);
            string longerPal = evenPal.size() > oddPal.size() ? evenPal : oddPal;
            maxPal = maxPal.size() > longerPal.size() ? maxPal : longerPal;
        }
        return maxPal;
    }

다만 주의 할 점은, sub string은 필요할 때만 해야 할 것이며, 

palindrom을 찾을 때 대상 sub string의 길이가 홀수냐 짝수냐에 따라 확장법이 달라지므로, 그 둘을 다 구해야 한다.  

 

만족할 만한 결과를 얻었다. 

 

Note) classic 한 DP 문제는 아니다. 

다만, idea 전환을 해야만 쉽게 풀 수 있는 문제가 될것인데, 이는 훈련으로 가능하다고 믿는다.