[LeetCode] Longest Palindrome Substring | 투포인터 | 파이썬 알고리즘 인터뷰, 정답, 소스코드

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

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

Longest Palindromic Substring - LeetCode

---

문제 요약

문자열이 주어질 때 가장 긴 팰린드롬 부분문자열을 구하라

---

핵심 전략

• 문자열이 한 글자로 이루어져 있거나 문자열 전체가 팰린드롬인 경우 입력 문자열을 그대로 반환한다. 
• 모든 인덱스에 대해 좌우로 확장하며 팰린드롬을 검사한다.

---

소스코드

class Solution:
    def longestPalindrome(self, s: str) -> str:

        if len(s) < 2 or s == s[::-1]:
            return s

        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]

        answer = ''
        for i in range(len(s) - 1):
            answer = max(answer, expand(i, i+1), expand(i, i + 2), key=len)

        return answer