[알고리즘][문자열 조작] - 6. 가장 긴 팰린드롬 부분 문자열

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/longest-palindromic-substring/

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

---

[중앙을 중심으로 확장하는 풀이]

• 최장 공통 부분 문자열(Longest Common Substring)이라는 문제가 있다. 
• 여러 개의 입력 문자열이 있을 때 서로 공통된 가장 긴 부분 문자열을 찾는 문제로 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제유형이다. 
• 그러나 이 문제는 DP로는 직관적으로 풀 수 없어 이해하기가 어렵고 실행속도가 매우 느리다

 

 

[투 포인터를 사용한 최장 공통 부분 문자열 구하기]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left:int, right:int) ->str
        #팰린드롬 판별 및 투 포인터 확장
            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

• 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이했다.
• 팰린드롬 판별만 하면 된다는 점에서 매칭이 될 때 중앙을 중심으로 점점 확장해나가며 가장 긴 팰린드롬을 판별하는 알고리즘이다.
• 팰린드롬은 bb처럼 짝수(2->4->6로 증가)일 때도 있고, bab처럼 홀수(1->3->5로 증가)일 때도 있다. 
• 따라서 짝수나 홀수 모든 경우에 대해 판별해야 한다.