[Medium] 5. Longest Palindromic Substring

길이 [1, 1000] 범위의 문자열 s가 주어지면, 그 안에서 가장 긴 팰린드롬을 찾아 반환하는 문제이다. 팰린드롬이란 "aba", "abba", "eye"처럼 거꾸로 읽어도 동일한 단어를 말한다.

문제 유형은 DP로 분류되어 있었는데, 처음엔 DP로는 어떻게 풀지 방법이 생각이 안나서 그냥 나이브한 방법으로 풀었고, 두 번째에는 디스커션을 확인하여 DP로 풀었다.

1)
우선 내가 푼 방법이다. 나는 s의 첫 문자부터 시작해서 끝까지 순회를 할 것이다. 현재 문자가 s[i]라면 맨 뒤에서부터 s[i]와 동일한 문자를 찾는다. 찾은 위치의 인덱스가 j라고 했을 때, [i, j] 범위를 검사하여 팰린드롬인지 확인한다. s[j]는 가장 뒤에서부터 찾은 문자이므로 s[i]에 대해선 가장 긴 팰린드롬이 된다. 때문에 s[i]에 대해선 더 검사할 필요없이 s[i+1]로 넘어간다. 

이때, s[j]를 그냥 선형 탐색하는 게 아니라, 탐색을 시작하기 전 <문자, 인덱스가 담긴 배열> 형태로 해시맵을 만들어 놓고, 이 인덱스가 담긴 배열에서 찾도록 하였다. 만약 key s[i]로 배열을 가져왔을 때 이 배열의 크기가 1이면 s[i]로 시작하는 팰린드롬은 없는 것이므로 s[i+1]로 넘어간다.

그리고 s[i]와 s[j]를 비교하기 전 [i, j] 범위의 길이가 현재까지 구해 놓은 팰린드롬의 최고 길이보다 작거나 같으면 확인할 필요가 없으므로 s[i+1]로 넘어간다. 이를 반복하면 된다.

2) DP를 사용하는 아이디어는 dp[i][j]를 [i, j] 범위의 문자열이 팰린드롬인지 여부로 정의하는 것이다. 즉 dp[i][j]가 true이면 s[i] == s[j]이고 s[i+1] == s[j-1], ... 이다. 탐색은 다음과 같은 순서로 한다.

s가 "babad"일 경우 

'd' 확인, 'a' 확인, 'ad' 확인, 'b'확인 'ba' 확인, 'bad' 확인, 'a' 확인, 'ab' 확인, 'aba' 확인, 'abad' 확인, ....

i가 시작을 나타내는 위치이고 j는 끝을 나타내는 위치이므로 "babad"에서 "abad"를 확인할 때 i는 1, j는 4가 된다. 만약 s[i] == s[j]라면 dp[i+1][j-1]이 true인지 확인하면 된다. "abad"는 s[i]==s[j]가 아니므로 넘어간다. 만약 "aba"일 경우 s[i]==s[j]이므로 내부를 확인해야 하는데, 이때 예외로 i와 j 사이의 간격(== j-i)이 3 미만이면(s[i]==s[j]인 상황에서) 무조건 팰린드롬이 되므로 해당 i, j는 true로 설정하면 된다.

만약 3 이상이라면 dp[i+1][j-1]을 확인하면 된다. 만약 true라면, dp[i][j]도 true가 된다. 이렇게 새로운 팰린드롬을 찾았으면 저장해둔 최고 길이와 비교하여 최고 길이의 팰린드롬을 업데이트하고 이를 반복하면 된다. 

 

SecondVersion()이 DP이다.

bool IsPalindrome(const string& s, int l, int r)
    {
        while(l < r)
        {
            if(s[l++] != s[r--])
                return false;
        }
        
        return true;
    }
    
    string FirstVersion(const string& s)
    {
        if(s.size() < 2)
            return s;

        
        // ex)
        // 'b' - 0,2
        // 'a' - 1,3
        // 'd' - 4
        unordered_map<char, vector<int>> umap;
        for(int i = 0; i < s.size(); ++i)
        {
            umap[s[i]].push_back(i);
        }
        
        
        // s[i]로 시작하는 팰린드롬 중 가장 긴 길이를 구한다.
        int maxLen = 0;
        string maxStr = "";
        for(int i = 0; i < s.size(); ++i)
        {
            // c가 존재하는 곳의 인덱스를 가진 벡터를 가져온다.
            char c = s[i];
            const vector<int>& indices = umap[c];
            
            // 근데 만약 사이즈가 1이면 c로 시작하는 팰린드롬은 없는 것
            if(indices.size() == 1)
                continue;
            
            auto beg = indices.begin();
            auto end = indices.end() - 1;
            int possibleMaxLen = *end - *beg + 1;
            if(possibleMaxLen <= maxLen)
                continue;
            
            while(beg != end)
            {
                int begIdx = i;
                int endIdx = *end;
                if(IsPalindrome(s, begIdx, endIdx))
                {
                    int len = (endIdx - begIdx) + 1;
                    if(len > maxLen)
                    {
                        maxLen = len;
                        maxStr = s.substr(i, len);
                        break;
                    }
                }
                
                --end;
            }
        }
        
        string ret = "";
        ret += s[0];
        
        return maxLen != 0 ? maxStr : ret;
    }
    
    string SecondVersion(const string& s)
    {
        int size = s.size();
        if(size < 2)
            return s;
        
        // dp[i][j]: [i, j] 범위의 문자열이 팰린드롬인지 여부
        vector<vector<bool>> dp(size, vector<bool>(size, false));
        int maxLen = 0;
        string ans;
        for(int i = size - 1; i >= 0; --i)
        {
            for(int j = i; j < size; ++j)
            {                
                // 양 끝의 문자가 같다면
                if(s[i] == s[j])
                {
                    // 내부를 검사
                    // 만약 두 문자 사이의 거리가 2 이하라면
                    // 무조건 팰린드롬
                    // ex) aba
                    // 그렇지 않다면 
                    // [i, j]보다 한 단계 좁은 범위인
                    // [i+1, j-1] 범위를 검사
                    int diff = j - i;
                    if(diff > 2)
                        dp[i][j] = dp[i+1][j-1];
                    else
                        dp[i][j] = true;
                    
                    // 만약 지금 범위가 팰린드롬이라면
                    // 기존 팰린드롬과 비교하여 크기가 더 크다면 업데이트
                    if(dp[i][j] == true)
                    {
                        int curLen = j - i + 1;
                       if(curLen > maxLen)
                       {
                           ans = s.substr(i, curLen);
                           maxLen = curLen;
                       }
                    }
                }
            }
        }
        
        return ans;
    }
    
    string longestPalindrome(string s) {
        // return FirstVersion(s);
        return SecondVersion(s);
    }