[파이썬 알고리즘 인터뷰] - 6장 (문자열 조작)

 

 

 

 

 

 

 

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

 

- 입력을 넣었을 때 가장 긴 팰린드롬 부분 문자열을 출력하라

 

 

ex) "babad" => "bab"      "cbbd" => "bb" 

 

 

 

 

 

 

 문제 상황

 

- LCS의 경우 dp로 해결할 수 있으나 이 문제의 경우 dp를 사용하면 오히려 속도가 느리게 나온다. 그래서 투 포인터 방식을 사용해야 한다.

 

 

 

 

 

 

 코드

 

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

 

 

 

 

 

 

 

 

 해설

 

- 기준점을 이동시키며 관찰한다. palindrome은 짝수 길이, 홀수 길이 모두 가능하므로 i+1, i+2까지 관찰한다.

 

 

- expand 함수가 조건에 벗어나기 전에 이미 left에 1이 줄어들고 right에 1이 늘어났으므로 보정이 필요하다. 그래서 출력을 left+1, right으로 해준다.