LeetCode 5. Longest Palindromic Substring with Python

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

1차 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬인지 확인하는 함수
        def checkPalindrome(s1, s2):
            s2 = s2[::-1]
            if s1 == s2:
                return True
            else:
                return False

        # 최대 길이
        m = 0
        l = len(s)

        # 문자 한개면 그대로 리턴
        if l == 1:
            return s
        answer = s[0]

        # 투포인터
        # 뒤에서 하나씩 빼면서 start 포인터와 같은 문자인지 확인
        for start in range(l-1):
            for end in range(l-1, start, -1):
                diff = end-start
                # 현재 최대길이보다 짧으면 비교 ㄴ
                if diff <= m :
                    break
                # 현재의 최대값보다 길이가 길고 같은 문자면
                if s[start] == s[end] and diff > m:
                    # 길이가 홀수 짝수를 다르게 비교
                    # 시작:중간 중간:끝 얘를 뒤집에서 똑같으면 팰린드롬 True -> 최대값, 답 갱신
                    if diff%2==0 and checkPalindrome(s[start:(start + end + 2) // 2], s[(start + end) // 2:end+1]):
                        m = diff
                        answer = s[start:end+1]
                        break
                    elif diff%2==1 and checkPalindrome(s[start:(start + end + 2) // 2], s[(start + end + 2) // 2:end+1]):
                        m = diff
                        answer = s[start:end+1]
                        break
        return answer

문제점

1. 코드 중복 존재
2. 느림...
   슬라이싱에서 성능 차이가 발생하는 것 같다.

Final Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            # 받아온 값 기준으로 left와 right값이 같으면 옆으로 계속 확장
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        # 문자 한개짜리거나 전체 뒤집었을 때 똑같으면 바로 리턴
        if len(s) < 2 or s == s[::-1]:
            return s

        result = ''
        for i in range(len(s)-1):
            # 중간값 없이 확장(bb), 중간값 있게 확장(bab)
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)

        return result

이렇게 하면 불필요한 뒤집기 및 슬라이싱을 하지 않아도 되서 훨씬 코드가 효율적이다.