Level 3. 가장 긴 팰린드롬

Level 3. 가장 긴 팰린드롬

 

 

긴 문자열부터 모든 부분 문자열을 확인하는 방법이지만, 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>

using namespace std;

int solution(string s)
{
    int answer = 0;
    size_t n = s.length();

    for (int len = n; 0 < len; --len)
        for (int ofs = 0; ofs + len <= n; ++ofs)
            if (s.substr(ofs, len) == string(s.rbegin() + n - len - ofs, s.rend() - ofs))
                return len;

    return 0;
}

 

모든 부분 문자열이 아닌, 투 포인터와 비슷하게 현재 지점부터 양쪽으로 펠린드롬인지 확인하는 방법이다.

• 이전보다 나은 점은 펠린드롬이 아닌 시점 이후로는 확인하지 않는다는 것이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int solution(string s)
{
    int answer = 0;
    size_t n = s.length();

    for (int i = 0; i < n; ++i)
    {
        int l = i, r = i;

        while ((0 <= l) && (r < n) && (s[l] == s[r]))
            --l, ++r;

        answer = max(answer, r - l - 1);

        l = i, r = i + 1;

        while ((0 <= l) && (r < n) && (s[l] == s[r]))
            --l, ++r;

        answer = max(answer, r - l - 1);
    }

    return answer;
}

 

DP를 이용한 방법이다.

• DP[i][j]는 i ~ j까지의 부분 문자열이 펠린드롬인지 저장한다.
• 길이를 1부터 증가시키면서 DP[i][j]의 경우 DP[i + 1][j - 1] == true와 s[i] == s[j]를 만족하면 펠린드롬이다.
• 짝수와 홀수를 고려해 길이 1, 2는 먼저 따로 처리해줘야 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(string s)
{
    int answer = 1;
    size_t n = s.length();
    vector<vector<bool>> DP(n, vector<bool>(n, false));

    for (int i = 0; i < n; ++i)
        DP[i][i] = true;

    for (int i = 0; i < n - 1; ++i)
        if (DP[i][i + 1] = (s[i] == s[i + 1]))
            answer = 2;

    for (int diff = 2; diff < n; ++diff)
    {
        for (int i = 0; i + diff < n; ++i)
        {
            int j = i + diff;

            if (DP[i + 1][j - 1] && (s[i] == s[j]))
            {
                DP[i][j] = true;
                answer = max(answer, diff + 1);
            }
        }
    }

    return answer;
}