[LeetCode] Longest Palindromic Substring

문제 출처

leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

문제

Given a string s, return the longest palindromic substring in s.

 

문자열 s가 주어졌을 때 가장 긴 palindromic 부분 문자열을 구하여라.

 

palindromic 문자열이 무엇일까?

 

왼쪽에서 오른쪽으로 읽으나 오른쪽에서 왼쪽으로 읽으나 같은 문자열을 말한다.

 

우리나라 말로 기러기, 토마토 등이 있다.

 

예시 1

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

 

"babad" 문자열에서 답은 "bab" 또는 "aba"가 될 수 있음을 보여준다.

 

가운데 문자 기준으로 좌우 대칭임을 유의하자. (문자열 길이가 홀수일 때)

예시 2

Input: s = "cbbd"
Output: "bb"

 

"cbbd" 문자열에서 답은 "bb"이다.

 

가운데 문자 없이 좌우 대칭임을 유의하자. (문자열 길이가 짝수일 때)

예시 3

Input: s = "a"
Output: "a"

 

예시 4

Input: s = "ac"
Output: "a"

 

문자 1개도 palindromic 문자열이 될 수 있다.

 

가장 긴 palindromic 부분 문자열의 길이가 1일 때 가장 앞에 있는 문자를 구하면 된다.

제약 사항

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

 

문자열 길이는 1 ~ 1000이고 문자열을 이루는 문자는 숫자 또는 영문 알파벳(대소문자 구분)이다.

 

우리는 어차피 문자 비교를 아스키코드값으로 하기 때문에 자동으로 대소문자 구분이 된다.

풀이

제일 먼저 가장 단순한 방법부터 생각해 보자.

 

그냥 문자열 전체를 돌면서 대칭인 부분 문자열을 찾는 것이다.

 

문자열 길이를 n이라고 했을 때 시간 복잡도와 공간 복잡도는 아래와 같을 것이다.

 

$$[Brute\,force]\;time\,complexity\,:\,O(n^3),\,space\,complexity\,:\,O(1)$$

 

문제 제약 사항에 시간 복잡도 제한은 없기 때문에 위 방법으로 풀어도 답은 잘 나온다.

 

하지만 동적 계획법(dynamic programming) 문제를 많이 접해본 사람이면 동적 계획법으로 풀 방법이 떠오를 것이다.

 

동적 계획법으로 풀기 위해 어떤 문제와 그 하위 문제 간의 관계를 먼저 파악해야 한다.

 

위 문제에서 어떤 부분 문자열이 palindromic 문자열이려면 첫 번째 문자와 마지막 문자가 같고

 

이 두 문자를 제외한 부분 문자열이 palindromic 문자열이어야 한다.

 

이렇게 상위 문제와 하위 문제간의 관계는 정의됐다.

 

부분 문자열들에 대해 palindromic 문자열 여부를 어딘가에 저장해 놓고

 

나중에 다시 해당 부분 문자열의 palindromic 문자열 여부를 알고자 할 때 바로 참고하면 될 것이다. 

 

코드로 표현하면 아래와 같다.

 

class Solution {
public:
    string longestPalindrome(string s) {
    	const size_t SIZE = s.size();
        vector<vector<char>> dp(SIZE, vector<char>(SIZE, 0));
        size_t left = 0, right = 0;
        for (size_t i = 0; i < SIZE; ++i)
        {
            for (size_t j = 0; j < i; ++j)
            {
                dp[j][i] = (s[i] == s[j]) && (i - j <= 2 || dp[j + 1][i - 1]);
                if (dp[j][i])
                {
                    if (i - j > right - left)
                    {
                        left = j;
                        right = i;
                    }
                }
            }
        }

        return s.substr(left, right - left + 1);
    }
}

 

변수 j는 부분 문자열 시작점을 나타내고 변수 i는 끝점을 나타낸다.

 

길이가 작은 부분 문자열부터 큰 부분 문자열 순서로 palindromic 문자열 여부를 결정하기 때문에

 

bottom-up 접근법이 되고 상위 문제를 풀기 위해 하위 문제의 결과를 바로 참고할 수 있다.

 

이 풀이 방식의 시간 복잡도와 공간 복잡도는 아래와 같다.

 

$$\,[Dynamic\,programming]\;time\,complexity\,:\,O(n^2),\,space\,complexity\,:\,O(n^2)$$

 

위 방법대로 배운 것을 잘 써먹어서 풀 때도 있지만 때로는 창의적으로 접근하여 쉽게 풀 때가 있다.

 

문자열을 순회하면서 각 문자가 중간에 위치한 것을 가정하고 가장 긴 palindromic 문자열을 찾는 것이다. 

 

palindromic 문자열은 가운데 또는 가운데 문자 기준으로 대칭을 이루는 특징을 이용한 것이다.

 

코드로 표현하면 아래와 같다.

 

class Solution {
private:
    void getSymmetry(string& s, size_t center, bool isEven, size_t& left, size_t& right)
    {
        if (isEven && s[center] != s[center + 1])
        {
            left = center, right = center;
            return;
        }
        else
        {
            left = center, right = isEven ? center + 1 : center;
            while (0 < left && right < s.size() && s[left - 1] == s[right + 1])
            {
                left--;
                right++;
            }
        }
    }

public:
    string longestPalindrome(string s) {
    	if (s.empty())
        {
            return "";
        }
        else if (1 == s.size())
        {
            return s;
        }

        const size_t SIZE = s.size();
        size_t min = 0, max = 0;
        for (size_t i = 0; i < SIZE - 1; ++i)
        {
            size_t left, right;
            // even
            getSymmetry(s, i, true, left, right);
            if (right - left > max - min)
            {
                min = left;
                max = right;
            }
            // odd
            getSymmetry(s, i, false, left, right);
            if (right - left > max - min)
            {
                min = left;
                max = right;
            }
        }

        return s.substr(min, max - min + 1);
    }
};

 

문자열을 순회하면서 각 문자 기준으로 2번의 대칭 확인을 한다.

 

예시에서 본대로 palindromic 문자열의 길이가 짝수 또는 홀수가 될 수 있기 때문이다.

 

이 풀이 방식의 시간 복잡도와 공간 복잡도는 아래와 같다.

 

$$\,[Expand\,around\,center]\;time\,complexity\,:\,O(n^2),\,space\,complexity\,:\,O(1)$$

 

동적 계획법보다 공간 복잡도가 더 좋은 것을 확인할 수 있다.

 

마지막으로 Manacher's Algorithm으로 가장 긴 palindromic 부분 문자열을 찾을 수 있다.

 

다음 게시물에서 소개하도록 하겠다.