[LeetCode][C++/Python] 5번: Longest Palindromic Substring (260)

 

생각의 흐름

이번 문제는 2가지 접근 방법이 있다.

 

사실 문제를 보면 바로 떠오르는 내용은 일반적으로 DP와 LCS(Longest Common Substring)이다.

따라서 나는 1) DP로 문제를 해결하려 노력하였다.

 

문제를 풀고 나니 보고 있는 책 에서는 2) 투포인터를 활용한 슬라이딩 윈도우 방식을 사용하였다. 

이 방식 또한 정리해볼까 한다.

 

1) DP방식 접근

우선 DP로 푸는 경우 DP[i][j]의 의미를 i번째 부터 j까지가 palindrome인 경우 True를 대입하도록 하였다.

따라서 재귀적으로 DP[i][j]이 palindrome이려면 DP[i+1][j-1]이 palindrome 이여야 하고, 또한 str[i] == str[j] 이여야 한다.

또한 가장 긴 팰린드롬인지 확인하기 위해서 max_len을 갱신해준다.

 

마지막으로 중심 시작 지점을 정한후 이를 기점으로 양 옆으로 확장해나가야 하는데, 이는 전부다 한번씩 중간이라 생각하고 시도해보는 방식으로 구현한다.

따라서 O(N^2)이 되는 방식이다.

 

2) 투포인터를 활용한 슬라이딩 윈도우 방식

이 방식도 직전의 방식처럼 모든 지점을 중심으로 두고 점점 확장해나가면서 확인하는 방식이다.

 

나의 코드

1. Python DP 풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        str_len = len(s)
        if str_len is 1:
            return s

        res = ""
        max_len = 0

        DP = [[0 for _ in range(str_len)] for _ in range(str_len)]

        for i in range(str_len - 1, -1, -1):
            for j in range(i, str_len):
                DP[i][j] = (s[i] == s[j]) and (j - i < 3 or DP[i + 1][j - 1])

                if DP[i][j] and (res == "" or j - i + 1 > max_len):
                    max_len = j - i + 1
                    res = s[i:i+max_len]

        return res

 

2. Python 투포인터

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s

        def if_is_palindrome_then_expand(left: int, right: int) -> str:
            while left >= 0 and right <= len(s) and s[left] == s[right-1]:
                left -= 1
                right += 1

            return s[left+1:right-1]

        res = ""
        for i in range(len(s) - 1):
            res = max(res, if_is_palindrome_then_expand(i, i + 3), if_is_palindrome_then_expand(i, i + 2), key=len)

        return res

 

3. C++

using namespace std;

string extend(int left, int right, string str) {
    while(left >= 0 && right < str.length() && str[left] == str[right]) {
        left -= 1;
        right += 1;
    }

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

class Solution {
public:
    string longestPalindrome(string s) {
        string temp = s;
        int str_len = s.length();

        reverse(temp.begin(), temp.end());
        if (str_len < 2 || s == temp) {
            return s;
        }

        string res = "";
        for(int i = 0; i < str_len; i++) {
            string s1 = extend(i, i + 2, s);
            string s2 = extend(i, i + 1, s);

            string t = (s1.length() < s2.length()) ? s2 : s1;
            res = (t.length() < res.length()) ? res : t;
        }

        return res;
    }
};