[Q6] 가장 긴 팰린드롬 부분 문자열

[리트코드 5] Longest Palindrome Substring

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

 

잘 모르겠어서, 교재에 적혀있는 풀이방법을 토대로 코딩했다.

내가 이해한 교재의 방식은 짝수 홀수의 슬라이딩 윈도우를 생성하여 앞으로 전진해가며, 그 윈도우의 크기를 확장하여 긴 팰린드롬을 찾는 방법이다.

 

먼저 팰린드롬인 문자열이 홀수의 자릿수 일수도, 짝수의 자릿수 일수도 있으므로 2개 모두 검사한다.

for i in range(len(s)-1):
    even = s[i:i+2]
    odd = s[i:i+1]
    
    if even == even[::-1]:
    	pass
    
    if odd == odd[::-1]:
    	pass

 

그 다음 문자열을 확장하여 가장 큰 팰린드롬 문자열을 리턴하는 함수를 만든다.

def expand(s, i, size):
    left = i
    right = i+size
    pelindrome = ''

    while left >= 0 and right <= len(s):
        word = s[left:right]
        if word == word[::-1]:
            pelindrome = word

        left -= 1
        right += 1

    return pelindrome

 

size는 위에서 생성한 홀수문자열인지 짝수문자열인지를 판단하기 위해 넣은 것이다.

좌우로 1칸씩 늘려가며 팰린드롬인지 확인하고 가장 긴 팰린드롬 문자열을 반환하는 함수이다.

 

생성한 expand 함수로 가장 긴 팰린드롬 문자열을 answer에 저장하며 확인한다.

for i in range(len(s)-1):
    even = s[i:i+2]
    odd = s[i:i+1]

    if even == even[::-1]:
        even = expand(s, i, 2)
        if len(answer) <= len(even):
            answer = even

    if odd == odd[::-1]:
        odd = expand(s, i, 1)
        if len(answer) <= len(odd):
            answer = odd

 

입력 값이 문자열 1개이거나, 가장 긴 팰린드롬이 문자열 그 자체일 경우 위와 같은 처리과정을 생략하기 위해 가장 위쪽 코드에 다음과 같이 예외처리를 한다.

if len(s) < 2 or s == s[::-1]:
    return s

 

정리하면 다음과 같다.

def longestPalindrome(self, s: str) -> str:
    def expand(s, i, size):
        left = i
        right = i+size
        pelindrome = ''

        while left >= 0 and right <= len(s):
            word = s[left:right]
            if word == word[::-1]:
                pelindrome = word

            left -= 1
            right += 1

        return pelindrome

    answer = ''

    if len(s) < 2 or s == s[::-1]:
        return s

    for i in range(len(s)-1):
        even = s[i:i+2]
        odd = s[i:i+1]

        if even == even[::-1]:
            even = expand(s, i, 2)
            if len(answer) <= len(even):
                answer = even

        if odd == odd[::-1]:
            odd = expand(s, i, 1)
            if len(answer) <= len(odd):
                answer = odd

    return answer