LeetCode - 5. Longest Palindromic Substring

문제 개요

난이도 - MEDIUM 사용 언어 - C++

Palindrome example

이번 문제는 주어진 문자열에서 가장 긴 회문(Palindrome)을 구하는 문제입니다.

회문은 위의 예시 이미지와 같이 문자열을 뒤집어도 동일한 문자열인 경우를 말합니다.

다만, 이번 문제에서는 주어진 문자열이 회문이 아닌, 문자열 내에서 회문인 가장 긴 부분 문자열을 반환하는 문제입니다.

문제 - LeetCode 5. Longest Palindromic Substring

풀이

Solution 1 - Brute force

첫 번째로 시도한 방법은 Brute force, 즉 2중 반복문으로 문자열을 i…j까지 i와 j를 1씩 늘려가며 회문인지 검사하고 반환하는 방법입니다.

for (int i = 0 ; i < s.size() ; i++)
{
    for (int j = i ; j < s.size() ; j++)
    {
        auto substr = std::string_view(&s[i], (j - i) + 1);
        if (isPalindrome(substr))
        {
            if (longestLength < (j - i) + 1)
            {
                longestLength = (j - i) + 1;
                start = i;
            }
        }
    }
}

return s.substr(start, longestLength);
...

bool isPalindrome(const std::string_view& s)
{
    auto length = s.size();

    for (std::size_t i = 0; i < length; i++)
    {
        if (s[i] != s[length - i - 1]) return false;
    }
    
    return true;
}

회문을 찾을 수 있는 아주 간단한 방법입니다.

제출 결과

Solution 1 result

하지만 위 코드를 제출하니 Time Limit Exceeded, 즉 시간 초과가 발생했습니다.

위 코드는 i..j까지 반복문을 순회할 때의 시간 복잡도가

$O(n^2)$

이고, 회문을 검사하는 코드의 시간 복잡도는

$O(n)$

입니다. 즉 최종적으로 시간 복잡도가

$O(n^3)$

인 코드이기 때문에, 매우 긴 문자열을 검사할 때 시간 초과가 발생했습니다.

코드 전문

#include <string>
#include <string_view>
#include <iostream>

class Solution 
{
public:
    std::string longestPalindrome(std::string s) 
    {
        if (s.size() == 1 || s.size() == 0) return s;

        int longestLength = 0;
        int start = 0;

        for (int i = 0 ; i < s.size() ; i++)
        {
            for (int j = i ; j < s.size() ; j++)
            {
                auto substr = std::string_view(&s[i], (j - i) + 1);
                if (isPalindrome(substr))
                {
                    if (longestLength < (j - i) + 1)
                    {
                        longestLength = (j - i) + 1;
                        start = i;
                    }
                }
            }
        }
        
        return s.substr(start, longestLength);
    }

private:
    bool isPalindrome(const std::string_view& s)
    {
        auto length = s.size();

        for (std::size_t i = 0; i < length; i++)
        {
            if (s[i] != s[length - i - 1]) return false;
        }
        
        return true;
    }
};

Solution 2 - Dynamic programming

두 번째 방법은 동적 프로그래밍(Dynamic programming)을 이용한 풀이입니다.

회문의 특성을 생각해보면, 만약 abcba라는 회문 문자열이 존재한다면 해당 문자열의 부분 문자열 bcb 또한 회문이며, bcb의 부분 문자열 c 또한 회문임을 알 수 있습니다.

또한 c처럼 문자가 하나인 경우는 무조건 회문입니다. 그리고 c의 앞뒤로 문자가 하나씩 추가될 때 두 문자가 같다면, 즉 bcb가 된다면 이 또한 회문이 됩니다.

이러한 특성과 동적 프로그래밍을 이용하면, 이미 회문을 검사한 문자열을 또 검사하지 않고도 새로운 회문 문자열을 찾을 수 있습니다.

먼저 규칙을 정의합니다.

S(i, j) : 문자열 S에 대해서 i번째부터 j번째까지의 부분 문자열
S(i, i) = 회문
S(i, i+1) = S_i == S_i+1일 경우 회문
S(i, j) = S(i+1, j-1) && S_i == S_j 일 경우 회문

2번 규칙에서 S(i, i)는 S 문자열의 i번째부터 i번째까지의 부분 문자열, 즉 문자 하나이므로 무조건 회문입니다.

3번 규칙은 S(i, i+1)에서 선택한 문자와 인접한 문자가 같다면 회문임을 나타냅니다. **“bb”**와 같은 경우입니다.

4번 규칙은 앞서 말했듯이, 부분 문자열이 회문이고 앞뒤로 추가되는 문자가 같다면 새로 확장된 문자열도 회문임을 나타냅니다.

std::vector<std::vector<bool>> dp(s.size(), std::vector<bool>(s.size(), false));

std::vector STL 컨테이너를 이용해 2차원 동적 배열을 선언합니다.

for (int j = 0 ; j < s.size() ; j++)
{
    for (int i = 0 ; i <= j ; i++)
    {
        bool same = s[i] == s[j];

        // 문자열 길이가 2 이상일 때는 dp[i + 1][j - 1], 즉 substr이 회문이어야 함
        // 문자열 길이가 2일 경우 (i, i+1) 두 문자가 같아야 회문
        // 문자열 길이가 1일 경우 무조건 회문
        dp[i][j] = j - i > 2 ? (dp[i + 1][j - 1] && same) : same;
        
        if ((longestLen < (j - i + 1)) && dp[i][j])
        {
            longestLen = j - i + 1;
            start = i;
        }
    }
}

i와 j는 각각 S(i, j)의 부분 문자열 시작 index인 i부터 j까지를 나타냅니다.

j - i가 2보다 작으면 규칙 2와 규칙 3을 적용할 수 있기에 단순히 S_i와 S_j를 비교한 결과가 저장됩니다.

j - i가 2보다 큰 경우는 문자열의 길이가 최소 3 이상이므로, 부분 문자열이 회문인지 검사하고 새로 추가된 문자 두 개가 같은지 확인해야 합니다. S(i, j)의 부분 문자열 S(i+1, j-1)은 이미 계산되어 배열에 저장되어 있을 테니, 추가로 계산할 필요 없이 값을 조회만 하면 됩니다.

마지막으로 지금 확인한 문자열이 회문이고 가장 길다면 해당 문자열의 인덱스를 저장합니다.

제출 결과

Solution 1 result

1번 해결 방법의 경우 O(n^3)이기 때문에 시간 초과가 발생했지만, 이번 방법의 경우 O(n^2)의 시간 복잡도이기 때문에 시간 초과가 발생하지 않았습니다.

784ms가 소요되었으며, 다른 C++ 코드 제출자에 비해 10% 정도의 성능밖에 보이지 않았습니다.

코드 전문

#include <string>
#include <string_view>
#include <iostream>
#include <vector>

class Solution 
{
public:
    std::string longestPalindrome(std::string s) 
    {
        if (s.size() == 1 || s.size() == 0) return s;

        int longestLen = 0;
        int start = 0;

        std::vector<std::vector<bool>> dp(s.size(), std::vector<bool>(s.size(), false));

        // 열 기반으로 탐색
        for (int j = 0 ; j < s.size() ; j++)
        {
            for (int i = 0 ; i <= j ; i++)
            {
                bool same = s[i] == s[j];

                // 문자열 길이가 2이상일때는 dp[i + 1][j - 1]즉, substr이 회문이여야 함
                // 문자열 길이가 2일경우(i, i+1) 두 문자가 같아야 회문
                // 문자열 길이가 1일경우 무조건 회문
                dp[i][j] = j - i > 2 ? (dp[i + 1][j - 1] && same) : same;
                
                if ((longestLen < (j - i + 1)) && dp[i][j])
                {
                    longestLen = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substr(start, longestLen);
    }
};

Solution 3 - Expand around center

회문을 검사할 때 문자열의 시작과 끝을 정해서 검사하는 방법도 있지만, 문자열의 가운데부터 좌우로 확장하면서 회문인지 검사하는 방법도 있습니다.

for (int i = 0 ; i < s.size() ; i++)
{
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, i + 1);
    int len = std::max(len1, len2);

    if (len > end - start)
    {
        start = i - (len - 1) / 2;
        end = i + len / 2;
    }
}

expandAroundCenter 함수는 i를 기준으로 좌우로 확장하며 회문인지 검사하는 함수입니다.

int expandAroundCenter(const std::string& s, int left, int right)
{
    while ( left >= 0 && right < s.size() && s[left] == s[right])
    {
        left--;
        right++;
    }

    return right - left - 1;
}

expandAroundCenter 함수를 i와 i+1에 대해 호출하는 이유는, 문자열 길이가 짝수인 경우 회문의 중앙 문자가 2개 존재할 수 있기 때문입니다. 이때는 두 경우 중 더 긴 문자열을 선택합니다.

제출 결과

Solution 3 result

이번 방법의 시간 복잡도는

$O(n^2)$

로 동적 프로그래밍과 동일합니다. 다만 공간 복잡도는 동적 프로그래밍이

$O(n^2)$

인 반면 이번 방법은 O(1)이기 때문에, 두 방법을 비교하면 메모리 사용량에서 큰 차이가 발생함을 확인할 수 있습니다.

코드 전문

#include <string>
#include <iostream>
#include <algorithm>

class Solution 
{
public:
    std::string longestPalindrome(std::string s) 
    {
        if (s.size() == 1 || s.size() == 0) return s;

        int start = 0;
        int end = 0;

        for (int i = 0 ; i < s.size() ; i++)
        {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = std::max(len1, len2);

            if (len > end - start)
            {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substr(start, (end - start) + 1);
    }
private:
    int expandAroundCenter(const std::string& s, int left, int right)
    {
        while ( left >= 0 && right < s.size() && s[left] == s[right])
        {
            left--;
            right++;
        }

        return right - left - 1;
    }
};