[LeetCode] 5. Longest Palindromic Substring

MinWoo Park·2021년 4월 19일

algorithm

Algorithm

목록 보기

30/42

Algorithm Problem with Python — 30day

문제 설명 📖

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

제한사항

1 <= s.length <= 1000
s consist of only digits and English letters (lower-case and/or upper-case),

입출력 예

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

문제 이해 🔑

가장 긴 팰린드롬 부분 문자열을 출력하는 문제입니다.

[LeetCode] 125. Valid Palindrome - Python에서 접했던 유형인데, palindrome(펠린드롬)은 우리말로 회문이라 부르며 앞뒤가 똑같은 단어나 문장을 말합니다.

팰린드롬 판별만 하면 되는 점을 착안하여 매칭이 될 때 중앙을 중심으로 점점 확장해 나가면서 가장 긴 팰린드롬을 판별하면 됩니다.

2,3칸으로 구성된 투 포인터가 슬라이딩 윈도우처럼 계속 앞으로 전진해나갑니다.
이 때 투 포인터 안에 들어온 문자열이 팰린드롬인 경우 그 자리에 멈춰서 점점 확장해 나갑니다.
그렇게 가장 긴 팰린드롬을 구할 수 있습니다.

수도 코드 ✍️

가장 먼저 예외처리를 합니다.
길이가 2보다 작거나 '토마토'처럼 뒤집어도 같은 문자열은 그 자체가 팰린드롬이기 때문에 앞선 두 경우 그대로 문자열을 리턴합니다.
함수를 모듈화 시킵니다.
팰린드롬을 만났을 때 중앙을 중심으로 확장하는 함수를 만듭니다.
함수는 포인터 역할을 해 줄 좌우측 숫자 타입의 값을 받습니다.
좌측이 0보다 크거나 같고 우측이 인풋 문자열의 길이보다 작은 동안 계속 확장하는 조건 그리고
확장할 좌우측의 문자가 같은 조건을 while문으로 작성합니다.
확장하는 동안 좌측에는 +1, 우측에는 -1을 더합니다.
while문이 끝나면 좌우측 값은 펠린드롬이 아닌 경우 확장이 멈춘 것이니 문자열을 슬라이싱할 때
slicing의 start에는 +1, end는 해당 문자 미포함이니 그대로 end로 슬라이싱합니다.
2번에 만든 함수를 사용할 건데 for문을 통해 슬라이딩 윈도우처럼 우측으로 이동할 겁니다.
문자열의 길이만큼 for문을 통해 반복하고 max 함수를 통해 가장 긴 팰린드롬을 리턴하도록 합니다.

코드 작성 ⌨️

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