[Python] Leet Code 5. Longest Palindromic Substring

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

class Solution:
    def longestPalindrome(self, s: str) -> str:

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

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

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

        return result        

이 문제에서 알아야할 포인트

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

return s[left+1:right]

• 문자열 슬라이싱
  • 가장 간단하면서도 잊어버리기 쉬운 포인트이다.
  • s[::-1]으로 간단하고 빠르게 문자열 뒤집기를 할 수 있다.
  • s[left+1:right]를 반환하는 이유는 그 전에 left와 right에 감소/증가가 한 번 적용되었기 때문이다.

expandStr(i,i+1)
expandStr(i,i+2)

• 슬라이딩 윈도우
  • 문자열 팰린드롬의 길이는 홀/짝이 모두 가능하다.
  • 홀수일 때는 (i,i+2)부터 확장이, 짝수일 때는 (i,i+1)부터 확장이 시작된다.

result = max(result, 
            expandStr(i,i+1),
            expandStr(i,i+2),
            key=len)

• max 키
  • key=len을 이용해 길이가 가장 긴 스트링을 반환한다.
  • for문을 돌면서 이전 결과에서 가장 긴 값이 result에 저장된다.