Python 알고리즘 인터뷰 - 문제6 가장 긴 팰린드롬 부분 문자열

leetcode 5. Longest Palindrome Substring

 

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

 

예제1

입력

'babad'

출력

'bab'

bab외에 aba도 정답.

 

예제2

입력

'cbbd'

출력

'bb'

 

풀이

두개의 sliding window를 사용하여 구현한다. 우선 짝수의 펠린드롬을 위한 sliding 윈도우를 기준으로 설명한다.

다음과 같은 'abccbe' 문자열이 있을 때 i, i+1을 포인터가 앞으로 진행을 한다.

팰린드롬을 만날 때까지 이동

 이 후 펠린드롬을 만나면 expand 함수를 호출하여 양쪽으로 확장을 진행한다. 

짝수 팰린드롬을 찾고 확장하는 과정

양쪽 확장은 s[L] == s[R] 일 때까지 진행하며, 더 이상 펠린드롬이 아닐 경우 s[L:R+1]을 반환한다.

s[L] == s[R] 일 때까지 진행하다가 s[L] != s[R]인 경우 stop

팰린드롬인 문자열의 범위는 L+1 ~ R-1이다. 파이썬 문자열 슬라이싱에서 인덱스 x ~ y 구간의 문자열을 반환하려면 s[x:y+1]으로 사용해야하며 따라서  s[L+1, R]을 반환해야 한다.

L<0, R > len(s)-1 인 경우도 확장을 진행하지 않는데 마찮가지로 s[L+1, R]로 반환하면 해당 범위의 팰린드롬을 구할 수 있다.

L<0 인 경우

R > len(s)-1인 경우

expand 함수를 코드로 나타내면 다음과 같다.

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

 

홀수 팰린드롬도 동일하게 expand함수를 i, i+2 파라미터를 사용하여 진행하면된다. "abbcbbd" 문자열을 예로 들면 다음과 같이 진행된다.

짝수 팰린드롬을 찾고 확장하는 과정

문자열이 1개이거나 전체 문자열이 팰린드롬인 경우는 해당 문자열을 그대로 반환하면 된다. 전체 문자열의 팰린드롬 확인은 s == s[::-1]로 가능하다. 

특수상황 예외처리

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

 

슬라이딩 윈도우를 진행하면서 각 i별 짝수 팰린드롬과 홀수 팰린드롬 중 문자열의 길이가 큰 값을 구해야한다. 파이썬의 max함수는 key = len으로 설정 시 각 파라미터의 길이를 비교하여 큰값을 반환한다. 이를 통해 가장 큰 문자열을 구하면 다음과 같다.

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

 

전체 코드

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

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

        return s[left + 1:right]

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

    return result