[리트코드 #5] 가장 긴 팰린드롬 부분 문자열

오늘은 '파이썬 알고리즘 인터뷰'를 참고했습니다.

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791189909178 

파이썬 알고리즘 인터뷰 - 교보문고

 

문제는 아래와 같습니다.

 

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

Longest Palindromic Substring - LeetCode

 

풀이 과정

 

저는 투포인터가 중앙을 중심으로 확장하는 형태로 풀이했습니다. 'babab'를 통해 가장 긴 팰린드롭을 구하는 풀이를 설명드리겠습니다.우선 [그림1]과 같이 길이가 2, 3인 두 개의 투포인터를 'babab'에 배치합니다.

[그림 1]

여기서 A와 같이 투포인터가 가리키는 시작점과 끝점의 원소가 같다면, 팰린드롭을 의미합니다. [그림 1]에서 'bab', 'aba' 가 있습니다.

 

하지만 'aba' (A)의 경우, 다른 팰린드롭과 다르게 양옆에 문자열이 있어서 양옆으로 투포인터를 확장할 수 있습니다. 확장하면 'babab'가 됩니다. 이 역시 양끝이 서로 같기 때문에 팰린드롭입니다. 

 

우리는 가장 긴 팰린드롭을 구해야되기 때문에, 'babab' 안에 있는 팰린드롭에서 가장 긴 길이의 투포인터를 구합니다.

 

코드

 

def answer(self,s):

	#팰린드롬 판별 및 투 포인터 확장
	def expand(left,right):
		while left>=0 and right<len(s) and s[left]==s[right]: #팰린드롬인 경우
    		left-=1 #투 포인터 양옆으로 확장
       		right+=1
    	return s[left+1:right]
	
    #해당 사항이 없을 때 빠르게 리턴
	if len(s)<2 or s==s[::-1]:
		return s
	
    result=''
	
    #슬라이딩 윈도우 우측으로 이동
	for i in range(len(s)-1):
		result=max(result,expand(i,i+1),expand(i,i+2),key=len)
 	return result