[4코3파] #281. Leetcode 5. Longest Palindromic Substring

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (281일차)
[4코1파] 2023.01.13~ (273일차)
[4코3파] 2023.10.01 ~ (11일차)

Today :

2023.10.11 [281일차]

5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

문제 설명

문자열이 주어졌을때 가장 긴 펠린드롬 부분문자열을 리턴한다.
펠린드롬 문자열은 '토마토', '기러기' 처럼 앞뒤를 뒤집어도 같은 문자열임.

문제 풀이 방법

brute force로 풀면 시간복잡도가 O(n^3)인데,
이진 탐색 하듯이 문자열을 돌면서 문자열 중심으로 왼쪽 ,오른쪽 문자열을 체크한다. O(n^2)으로 해결할 수 있음.

내 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        resLen = 0
        for i in range(len(s)):
            l,r = i, i
            while l>=0 and r<len(s) and s[l]==s[r]:
                if (r-l+1)>resLen:
                    res = s[l:r+1]
                    resLen = r-l+1
                l-=1
                r+=1
            l,r = i,i+1
            while l>=0 and r<len(s) and s[l]==s[r]:
                if (r-l+1) > resLen:
                    res = s[l:r+1]
                    resLen = r-l+1
                l-=1
                r+=1
        return res

증빙

여담

초큼.. 어렵네...