[Leetcode] 5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

어떤 문자열 안에서 가장 긴 펠린드롬을 찾아내는 문제이다. 양 끝에서 오면서 비교하면 O(n)으로 가능하겠다 싶어서 그렇게 시도를 했다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        i = 0
        j = len(s)

        while i < j:
            length = j - i
            half = length // 2

            if s[i:i+half] == s[j-1:j-half:-1]:
                return s[i:j]
            

        return 

이런 식으로 코드를 작성하기 시작했는데 처음엔 완벽하다고 생각했으나 i와 j를 움직이는 기준을 정하지 못해서 헤맸다. 도저히 답이 안 나와서 GPT한테 물어봤다.

GPT는 Center Expansion이라는 기법을 추천했다. 중앙에서부터 i와 j를 조건이 맞을 때까지 벌려가면서 답을 구하는 방법이다. 내가 문제에서 놓쳤던 것 중 하나가 문자열의 최대 길이가 최대 1,000이라서 O(n^2)도 커버할만한데 O(n)에서 머리가 고정돼서 다른 방법 시도해볼 생각을 못 했다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        answer = ""
        for i in range(len(s)):
            left = right = i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            odd = s[left+1:right]

            if len(odd) > len(answer):
                answer = odd

            left = i
            right = i+1

            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            even = s[left+1:right]

            if len(even) > len(answer):
                answer = even

        return answer

여튼 비슷한 문제가 나오면 사이즈 보고 괜찮을 것 같으면 중앙 확장 방법도 시도해봐야겠다.