[LeetCode] #5. Longest Palindromic Substring (python)

문제

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

Longest Palindromic Substring - LeetCode

주어진 문자열에서 가장 긴 팰린드롬 문자열을 반환해야 한다.

 

예시 입출력

Input: s = "babad"
Output: "bab"

 

 

 

풀이

 

책 풀이

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별 및 투 포인터 확장
        def expand(left: int, right: int) -> str:
            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):
            result = max(result,
                         expand(i, i + 1),
                         expand(i, i + 2),
                         key=len)
        return result

 

우선 주어진 글자가 한글자거나 전체가 팰린드롬인 경우는 먼저 처리한다.

끝 글자가 같다면 포인터를 확장하는 함수인 expand 함수를 정의한다.

expand 함수에서 return할 때 left+1을 한 이유

⇒ 만약에 팰린드롬이면 포인터가 확장되는데 확장되고 나서 조건에 해당하지 않으면 다시 이전 문자열로 가야하기 때문에 left+1을 해줘야 한다. right은 원래 인덱싱 끝부분은 -1이라서 따로 처리하지 않은 것이다.

 

포인터는 짝수, 홀수 모든 경우를 판별하기 위해 expand 함수를 두번 사용했다. max 함수에 key=len을 설정해서 길이를 기준으로 최대값을 반환한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰