greentea31's Note

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

풀이 과정

문자열 내에서 가장 긴 팰린드롬 부분 문자열을 구하는 문제이다.

팰린드롬 문자열은 뒤집어도 뒤집기 전의 문자열과 같은 문자열을 의미한다. DP로 풀 수 있는 잘 알려져 있는 문제이지만 O(N^2)로 부분 문자열을 확장해가며 해결하였다.

다음과 같은 알고리즘을 구현해 문제를 해결하였다.

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(i):
            left, right = i, i
            while left >= 0:
                if s[i] == s[left]:
                    left -= 1
                else:
                    break
            while right <= len(s) -1:
                if s[i] == s[right]:
                    right += 1
                else:
                    break
            
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    left -= 1
                    right += 1
                else:
                    break
            
            return s[left+1:right]
                
        answer = ''
        for i in range(len(s)):
            answer = max(answer, expand(i), key=len)
        return answer