LeetCode 5. (Medium) Longest Palindromic Substring - 가장 긴 팰린드롬 (python)

문제 

Longest Palindromic Substring - LeetCode

문자열에서 가장 긴 팰린드롬 문자열을 추출하는 문제이다. (팰린드롬 : 앞뒤가 똑같은 문자열)

 

(연관문제 : 유효한 팰린드롬)

LeetCode 125. Valid Palindrome - 유효한 팰린드롬 (python)

 

예제

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

 

풀이 (python)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def expand(l:int, r:int)->str: #left, right 이중 포인터
            while l>=0 and r<len(s) and s[l]==s[r]:
                l-=1
                r+=1
            return s[l+1:r] # 인덱스 l부터 r-1까지 
        
        result = ''
        
        if len(s)<2 or s==s[::-1]:  #예외처리
            return s
        
        for i in range(len(s)-1):
            result = max(result,
                         expand(i, i+1), #팰린드롬 길이가 짝수인 경우
                         expand(i, i+2), #팰린드롬 길이가 홀수인 경우
                         key=len)
                         
        return result

투 포인트를 사용해 팰린드롬 길이가 짝수/홀수 인 경우를 구분했고

인덱스를 확장하며 팰린드롬을 리턴하는 expand(left, right) 함수를 만들어 길이 기준 (key=len)으로

최대길이 문자열을 반환했다.