[LeetCode] 5. Longest Palindromic Substring [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Longest Palindromic Substring - LeetCode>

1. 문제 (가장 긴 팰린드롬 부분 문자열)

가장 긴 펠린드롬 부분 문자열을 출력하라.
(정답이 여러개 일 수 있는데 나는 가장 첫번째 부분 문자열을 출력하겠다.)

2. 풀이

• 투 포인터를 이용한 풀이

(출처)

• 그림과 같이 2칸, 3칸으로 구성된 투 포인터를 슬라이딩 윈도우처럼 오른쪽으로 한칸씩 이동하며 팰린드롬을 확인한다.

3. 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 팰린드롬 판별 및 포인터 확장
        def expand(left, right):
            while left >= 0 and right <= len(s) and s[left] == s[right-1]:
                left -= 1
                right += 1
            return s[left+1 : right-1]

        # 종료 조건
        if len(s) < 2 or s == s[::-1]:
            return s

        ret = ''
        # 슬라이딩 윈도우를 왼쪽부터 오른쪽으로
        for i in range(len(s)-1): 
            ret = max(ret, expand(i, i+1), expand(i, i+2), key=len) 

        return ret

• 결과 :

방식	Status	Runtime	Memory	Language
투 포인터	[Accepted]	284 ms	14.5 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋