[Q. 06] 가장 긴 팰린드롬 부분 문자열

가장 긴 팰린드롬 부분 문자열을 출력하라.

 

팰린드롬을 확인할 문자열은 짝수 길이의 문자열, 홀수 길이의 문자열 2가지 종류가 있다.

그 전에 먼저 문자열에서 가장 긴 팰린드롬 문자열을 뽑는 함수를 만든다.

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

    return s[left+1:right]

 

left와 right를 좌우로 한칸씩 늘려가며 확인한다. 만약 처음부터 while 조건에 맞지 않는다면, s[left+1:right]를 return 한다.

그리고 문자열 처음부터 2칸, 3칸 문자로 잘라서 expand함수로 가장 큰 길이의 팰린드롬 문자열을 찾는다. 그리고 그 결과들과 기존에 있던 결과 중 가장 긴 결과를 찾는다.

answer = ''

if len(s) == 0 or len(s) == 1:
    return s

for i in range(len(s)-1):
    answer = max(answer, expand(i, i+1, s), expand(i, i+2, s), key=len)

 

전체 코드는 다음과 같다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int, s: str) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1

            return s[left+1:right]

        answer = ''

        if len(s) == 0 or len(s) == 1:
            return s

        for i in range(len(s)-1):
            answer = max(answer, expand(i, i+1, s), expand(i, i+2, s), key=len)
            
        return answer