(Python) 5 Longest Palindromic Substring

리트코드 LeetCode 5 Longest Palindromic Substring 문제의 파이썬 python 풀이입니다.

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

문제

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

Constraints

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

풀이

투 포인트를 활용한 슬라이딩 윈도우 방식으로 풀어보겠습니다.

확장 함수 선언

# 투 포인터 확장 함수 선언
        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]
    

주어진 left와 right를 기준으로, 팰린드롬인지 확인하며 양쪽으로 확장해 나가는 함수입니다.

• 예시
  • ‘abba’에서 left=1, right=2이면 → “bb”에서 “abba”까지 확장 가능
• left + 1 : right를 리턴하는 이유
  • while 루프가 끝날 때는 한 번 더 초과한 상태라, 올바른 구간을 잘라야 함

# 예시
s = "racecar"
expand(3, 3) → "racecar"  ← 가운데가 'e'인 홀수 팰린드롬
expand(2, 3) → "cec"      ← 가운데가 'ce'인 짝수 팰린드롬

슬라이딩 윈도우

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

• 각 문자 위치 i를 기준으로
  • expand(i, i+1) → 짝수 길이 팰린드롬 시도 (ex: "abba")
  • expand(i, i+2) → 홀수 길이 팰린드롬 시도 (ex: "racecar")
    • 홀수 길이 팰린드롬 조사는 expand(i, i)로 시작할 수도 있음. 하지만 어차피 한 글자 문자열이기 때문에, 세 글자 문자열부터 조사를 하는 것이 효율적
• max(..., key=len) → 세 후보 중에서 가장 긴 팰린드롬 문자열을 선택해서 result에 저장

왜 i+1, i+2를 쓸까?

• 팰린드롬은 중심을 기준으로 좌우 대칭이기 때문에,
  • 중심이 하나일 수도 있고 (expand(i, i+2) → 홀수)
  • 중심이 두 개일 수도 있음 (expand(i, i+1) → 짝수)

그래서 둘 다 시도해 보고, 더 긴 쪽을 선택

• max(...)로 현재 result보다 더 긴 팰린드롬이 나오면 업데이트함
  
  

for i in range(0, len(s) - 1) 루프 과정

for i in range(0, len(s) - 1)
→ 각 위치에서 expand(i, i+1) (짝수) 와 expand(i, i+2) (홀수) 수행

🔹 i = 0

• expand(0, 1) → b ≠ a → 팰린드롬 X → return ""
• expand(0, 2) → b == b, 그다음 a == a → 팰린드롬 "bab"
  → 현재 result: "bab"

🔹 i = 1

• expand(1, 2) → a ≠ b → return ""
• expand(1, 3) → a == a, 그다음 b == b → 팰린드롬 "aba"
  → 길이 같음. "bab" 또는 "aba" 중 하나 유지

🔹 i = 2

• expand(2, 3) → b ≠ a → return ""
• expand(2, 4) → b ≠ d → return ""

🔹 i = 3

• expand(3, 4) → a ≠ d → return ""
• expand(3, 5) → 범위 벗어남 → return ""

정답 코드

# 가장 긴 펠린드롬 수 : 투 포인트, 슬라이딩 윈도우 방식 응용
 
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]
 
        # 길이가 1 이하거나, 뒤집어도 똑같은 그 자체로 펠린드롬인 경우
        if len(s) < 2 or s == s[::-1]:
            return s
 
        result = ''
        
        # 슬라이딩 윈도우 우측 이동
        for i in range(0, len(s)-1):
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)
 
        return result