가장 긴 펠리드롬

문제이동
문자열 속에서 가장 긴 펠린드롬을 찾는 문제

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(i, j):
            while 0<=i and j<len(s) and s[i] == s[j]:
                i -= 1
                j += 1
            return s[i+1:j]
        
        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

홀수, 짝수 별로 두 포인터를 사용해서 문자를 비교하며 확장하는 방식이다.
i, i+1 : 짝수 (슬라이딩 윈도우의 초기 길이가 2)
i, i+2 : 홀수 (초기 길이가 3)

+) 다시 풀렴

• 일하다가 지력을 다 썼는지 이걸 한참 못 풀었었다.
  (오답노트 : 다음에 또 풀어볼 문제로 찜^^...)

• 문자열 속에서 가장 긴 펠린드롬을 찾는 문제는

• 짝수, 홀수 별 슬라이딩 윈도우를 이동 및 확장시키는 느낌이다.

• 현재 인덱스(윈도우의 현재 위치, 중심)을 기준으로 생성된 왼쪽 포인터, 오른쪽 포인터를 점점 확장시켜간다.

• 최종적으로 최대 길이는 어떻게 구하나 싶었는데 그냥
  result = max(result, expand(), expand(), len=key)
  로 하는 거였다.

• 문자열 길이가 최소일 때와 최대일 때의 예외처리를 해줘야 한다.