[ 파이썬 알고리즘 인터뷰 ] 가장 긴 팰린드롬 부분 문자열

문제1. 가장 긴 팰린드롬 부분 문자열

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

 

EX1_입력 ] "babad"
EX1_출력 ] "bab" 또는 "aba"

EX2_입력 ] "cbbd"
EX2_출력 ] "bb"

 

해당 문제를 푸는 아이디어?!

- 슬라이딩 윈도우 기반 투 포인터!

- 중앙을 중심으로 확장

 

 

아이디어 1. 슬라이딩 윈도우 기반 투 포인터!

 

- 2칸, 3칸으로 구성된 투 포인터가 슬라이딩 윈도우 처럼 전진한다. bb 또는 bab 등 중심을 기준으로 앞뒤 문자열이 같기에 2,3칸으로 구성된 포인터를 사용하면 팰린드롬을 찾아낼 수 있다. 문자열이 끝날 때까지 포인터가 앞으로 전진해나가며 팰린드롬을 찾는다. 2칸짜리 포인터는 짝수용 팰린드롬을, 3칸 짜리 포인터는 홀수용 팰린드롬을 찾기위함이다. 

 

 

아이디어 2. 중앙을 중심으로 확장!

- 슬라이딩 윈도우 기반 포인터의 양끝 문자열이 같다면 슬라이딩을 확장한다. 위 그림에서 3칸짜리 포인터의 양끝이 4로 같다면 왼쪽 -1, 오른쪽 +1 로 슬라이딩 크기를 확장하여 양 옆의 문자열도 확인한다. 더 긴 팰린드롬인지를 확인하기 위해 포인터의 양끝이 같지 않을 때까지 슬라이딩의 크기를 확장해간다!

 

 

def longestPalindrome(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

teststr ="babad"
longestPalindrome(teststr)

 

- while문 안에서 돌다가 포인터의 양끝이 달라서 return을 해야할 경우 , s[ left +1, right ]를 해주어야하는 것을 주의! 이미 while문을 빠져나오기 전 left가 -1 이 되었으니 +1을 해주고, right의 경우 문자열 슬라이싱 자체가 n-1만큼 출력되니 그대로 써주면 된다! ( EX. S="12345" 의 S[1:3]는 "23" )

 

- 문자열 길이가 2보다 작거나 ( 즉 그냥 1인 경우 = 팰린드롬 ) 문자열의 역순이 문자열과 같다면 팰린드롬이므로 그냥 문자열 자체를 반환한다. 

 

- EXPAND함수에서 반환된 문자열과 RESULT의 문자열 중 가장 긴 문자열을 다시 RESULT에 저장한다. FOR문이 종료되면 최종적으로 저장된 RESULT를 반환한다. 

 

---

[ 참고자료 ]

- 도서 : 파이썬 알고리즘 인터뷰 

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