[Python] leetcode-5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

문제는 간단하다!
문자열 s 안에서 앞뒤가 똑같이 읽히는 가장 긴 부분 문자열을 찾아야 한다.
예를 들어 "babad"의 경우 "bab" 또는 "aba" 모두 정답이다.

팰린드롬(palindrome)이란, 앞뒤가 같은 문자열을 말한다.
즉, 문자열을 중심 기준으로 양쪽 문자가 대칭을 이룬다.

예를 들어,

• "aba"는 중심 'b'를 기준으로 양쪽 'a'가 같다.
• "abba"는 중심이 두 글자('bb') 사이에 있다.

즉, 모든 팰린드롬은 어떤 중심을 기준으로 양쪽으로 확장할 수 있다.

---

1️⃣ 문자열의 각 인덱스를 중심으로 설정한다.
2️⃣ 홀수 길이(aba 형태)와 짝수 길이(abba 형태)를 각각 확인한다.
3️⃣ 중심에서 좌우로 같은 문자가 나오는 한 계속 확장한다.
4️⃣ 가장 긴 구간을 갱신한다.

---

🐋정답 코드🐋

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s or len(s)<2:
            return s

        start,end=0,0
        def expand(l,r):
            while 0<=l and r<len(s) and s[l]==s[r]:
                l-=1
                r+=1
            return l+1,r-1
        
        for i in range(len(s)):
            l1,r1=expand(i,i)
            l2,r2=expand(i,i+1)
            
            if r1-l1>r2-l2:
                curr_l,curr_r=l1,r1
            else:
                curr_l,curr_r=l2,r2
            
            if curr_r-curr_l>end-start:
                start,end=curr_l,curr_r

        return s[start:end+1]