파이썬 알고리즘 인터뷰 6장 6번 가장 긴 팰린드롬 문자열 (리트코드 5번)

Kim Yongbin·2023년 8월 13일

리트코드 코딩테스트 파이썬 파이썬 알고리즘 인터뷰

코딩테스트

목록 보기

6/162

Problem

LeetCode - The World's Leading Online Programming Learning Platform

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

주어진 문자열에서 가장 긴 팰린드롬 문자열을 찾아라

Solution

일단, 이 문제는 못 풀었다. 내부에서 어떤 식으로 찾아야할지 감이 오지 않았다.

이 문제의 해법은 투 포인트를 사용한 슬라이딩 알고리즘이다.

Sliding Window 알고리즘

슬라이딩 윈도우 알고리즘은 고정된 사이즈의 윈도우를 좌 또는 우로 움직이면서 해당 범위에 있는 값들을 활용하여 연산을 하는 것이다. 공통된 부분은 유지하고 처음과 끝의 원소만 갱신하면서 유용하게 사용하는 것이다.

Two pointer 알고리즘

투 포인터 알고리즘의 경우 1차원 배열에 2개의 포인터를 조작하면서 연산을 처리하는 알고리즘이다. 완전 탐색으로 진행할 경우 시간초과가 되는 문제들의 시간 복잡도를 줄이는데 유용하다.

풀이

class Solution:
    @staticmethod
    def expand(left, right, s):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1: right]

    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2 or s == s[::-1]:
            return s

        result = ""
        for i in range(len(s)):
            result = max(result, self.expand(i, i, s), self.expand(i, i+1, s), key=len)
        return result